{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Perfect Rectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #line-sweep"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #扫描线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isRectangleCover"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完美矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个数组 <code>rectangles</code> ，其中 <code>rectangles[i] = [x<sub>i</sub>, y<sub>i</sub>, a<sub>i</sub>, b<sub>i</sub>]</code> 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 <code>(x<sub>i</sub>, y<sub>i</sub>)</code> ，右上顶点是 <code>(a<sub>i</sub>, b<sub>i</sub>)</code> 。</p>\n",
    "\n",
    "<p>如果所有矩形一起精确覆盖了某个矩形区域，则返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/27/perectrec1-plane.jpg\" style=\"height: 294px; width: 300px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>5 个矩形一起可以精确地覆盖一个矩形区域。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/27/perfectrec2-plane.jpg\" style=\"height: 294px; width: 300px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>两个矩形之间有间隔，无法覆盖成一个矩形。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/27/perfecrrec4-plane.jpg\" style=\"height: 294px; width: 300px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= rectangles.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>rectangles[i].length == 4</code></li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= x<sub>i</sub>, y<sub>i</sub>, a<sub>i</sub>, b<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [perfect-rectangle](https://leetcode.cn/problems/perfect-rectangle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [perfect-rectangle](https://leetcode.cn/problems/perfect-rectangle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]', '[[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]', '[[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isRectangleCover(self, rectangles):\n",
    "        \"\"\"\n",
    "        :type rectangles: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        mx,my,ma,mb = rectangles[0]\n",
    "        s,s1,s2,s3 = 0,0,0,0\n",
    "        for x,y,a,b in rectangles:\n",
    "            mx,my,ma,mb = min(mx,x),min(my,y),max(ma,a),max(mb,b)\n",
    "            x1,x2,y1,y2 = a-x,a*a-x*x,b-y,b*b-y*y\n",
    "            s += x1*y1\n",
    "            s1 += x2*y1\n",
    "            s2 += x1*y2\n",
    "            s3 += x2*y2\n",
    "        return s==(ma-mx)*(mb-my) and s1==(ma*ma-mx*mx)*(mb-my) and s2 == (ma-mx)*(mb*mb-my*my) and s3==(ma*ma-mx*mx)*(mb*mb-my*my)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        mx, my, ma, mb = rectangles[0]\n",
    "        s, s1, s2, s3 = 0, 0, 0, 0\n",
    "        for x,y,a,b in rectangles:\n",
    "            mx,my,ma,mb = min(mx,x),min(my,y),max(ma,a),max(mb,b)\n",
    "            x1,x2,y1,y2 = a-x,a*a-x*x,b-y,b*b-y*y\n",
    "            s += x1*y1\n",
    "            s1 += x2*y1\n",
    "            s2 += x1*y2\n",
    "            s3 += x2*y2\n",
    "        return s==(ma-mx)*(mb-my) and \\\n",
    "        s1==(ma*ma-mx*mx)*(mb-my) and \\\n",
    "        s2 == (ma-mx)*(mb*mb-my*my) and \\\n",
    "        s3==(ma*ma-mx*mx)*(mb*mb-my*my)\n",
    "        \n",
    "    # solve 2, hash table\n",
    "    def isRectangleCover2(self, rectangles: List[List[int]]) -> bool:\n",
    "        area, minX, minY, maxX, maxY = 0, rectangles[0][0], rectangles[0][1], rectangles[0][2], rectangles[0][3]\n",
    "        cnt = defaultdict(int)\n",
    "        for rect in rectangles:\n",
    "            x, y, a, b = rect[0], rect[1], rect[2], rect[3]\n",
    "            area += (a - x) * (b - y)\n",
    "\n",
    "            minX = min(minX, x)\n",
    "            minY = min(minY, y)\n",
    "            maxX = max(maxX, a)\n",
    "            maxY = max(maxY, b)\n",
    "\n",
    "            cnt[(x, y)] += 1\n",
    "            cnt[(x, b)] += 1\n",
    "            cnt[(a, y)] += 1\n",
    "            cnt[(a, b)] += 1\n",
    "\n",
    "        if area != (maxX - minX) * (maxY - minY) or cnt[(minX, minY)] != 1 or cnt[(minX, maxY)] != 1 or cnt[(maxX, minY)] != 1 or cnt[(maxX, maxY)] != 1:\n",
    "            return False\n",
    "\n",
    "        del cnt[(minX, minY)], cnt[(minX, maxY)], cnt[(maxX, minY)], cnt[(maxX, maxY)]\n",
    "\n",
    "        return all(c == 2 or c == 4 for c in cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        rectangles.sort()\n",
    "        h = []\n",
    "        total = 0\n",
    "        ys = SortedList()\n",
    "        l = d = float('inf')\n",
    "        r = u = -float('inf')\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            l = min(l, x1)\n",
    "            d = min(d, y1)\n",
    "            r = max(r, x2)\n",
    "            u = max(u, y2)\n",
    "            total += (x2 - x1) * (y2 - y1)\n",
    "            while h and h[0][0] <= x1:\n",
    "                _, mi, ma = heappop(h)\n",
    "                ys.discard(mi)\n",
    "                ys.discard(ma)\n",
    "            i, j = bisect_right(ys, y1), bisect_left(ys, y2)\n",
    "            if i != j or i & 1:\n",
    "                return False\n",
    "            heappush(h, (x2, y1, y2))\n",
    "            ys.add(y1)\n",
    "            ys.add(y2)\n",
    "        return total == (r - l) * (u - d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\r\n",
    "    def isRectangleCover(self, rectangles):\r\n",
    "        \"\"\"\r\n",
    "        :type rectangles: List[List[int]]\r\n",
    "        :rtype: bool\r\n",
    "        \"\"\"\r\n",
    "        mx,my,ma,mb = rectangles[0]\r\n",
    "        s,s1,s2,s3 = 0,0,0,0\r\n",
    "        for x,y,a,b in rectangles:\r\n",
    "            mx,my,ma,mb = min(mx,x),min(my,y),max(ma,a),max(mb,b)\r\n",
    "            x1,x2,y1,y2 = a-x,a*a-x*x,b-y,b*b-y*y\r\n",
    "            s += x1*y1\r\n",
    "            s1 += x2*y1\r\n",
    "            s2 += x1*y2\r\n",
    "            s3 += x2*y2\r\n",
    "        return s==(ma-mx)*(mb-my) and s1==(ma*ma-mx*mx)*(mb-my) and s2 == (ma-mx)*(mb*mb-my*my) and s3==(ma*ma-mx*mx)*(mb*mb-my*my)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        x_min = y_min = float('inf')\n",
    "        a_max = b_max = float('-inf')\n",
    "        s = [0] * 4\n",
    "        for x, y, a, b in rectangles:\n",
    "            for i, (m1, m2) in enumerate(itertools.product([a - x, a * a - x * x], [b - y, b * b - y * y])):\n",
    "                s[i] += m1 * m2\n",
    "            x_min = min(x_min, x)\n",
    "            y_min = min(y_min, y)\n",
    "            a_max = max(a_max, a)\n",
    "            b_max = max(b_max, b)\n",
    "        \n",
    "        s0 = [m1 * m2 for m1, m2 in itertools.product([a_max - x_min, a_max * a_max - x_min * x_min], [b_max - y_min, b_max * b_max - y_min * y_min])]\n",
    "        #print(s0, s)\n",
    "        return s0 == s\n",
    "            \n",
    "                    \n",
    "\n",
    "        \n",
    "\n",
    "    def isRectangleCover0(self, rectangles: List[List[int]]) -> bool:\n",
    "        x_min = y_min = float('inf')\n",
    "        a_max = b_max = float('-inf')\n",
    "        area = 0\n",
    "        counter = collections.defaultdict(int)\n",
    "        for x, y, a, b in rectangles:\n",
    "            x_min = min(x_min, x)\n",
    "            y_min = min(y_min, y)\n",
    "            a_max = max(a_max, a)\n",
    "            b_max = max(b_max, b)\n",
    "            counter[(x, y)] += 1\n",
    "            counter[(x, b)] += 1\n",
    "            counter[(a, y)] += 1\n",
    "            counter[(a, b)] += 1\n",
    "            area += (a - x) * (b - y)\n",
    "        \n",
    "        if area != (a_max - x_min) * (b_max -  y_min):\n",
    "            return False\n",
    "\n",
    "        for x in [x_min, a_max]:\n",
    "            for y in [y_min, b_max]:\n",
    "                if (x, y) not in counter or counter.pop((x, y)) != 1:\n",
    "                    return False\n",
    "        \n",
    "        for v in counter.values():\n",
    "            if v != 2 and v != 4:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "    def isRectangleCover_failed(self, rectangles: List[List[int]]) -> bool:\n",
    "        n = len(rectangles)\n",
    "        vertice = [[0] * n for _ in range(4)]\n",
    "        area = 0\n",
    "\n",
    "        for i, rectangle in enumerate(rectangles):\n",
    "            area += (rectangle[3] - rectangle[1]) * (rectangle[2] - rectangle[0])\n",
    "            for j, vertex in enumerate(rectangle):\n",
    "                vertice[j][i] = vertex\n",
    "        \n",
    "        xx, yy, aa, bb = min(vertice[0]), min(vertice[1]), max(vertice[2]), max(vertice[3])\n",
    "        if area != (aa - xx) * (bb - yy):\n",
    "            return False\n",
    "        \n",
    "        def overlap(rectangle1, rectangle2):\n",
    "            x1, y1, a1, b1 = rectangle1\n",
    "            x2, y2, a2, b2 = rectangle2\n",
    "            if x1 >= a2 or x2 >= a1 or y1 >= b2 or y2 >= b1:\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                if overlap(rectangles[i], rectangles[j]):\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        line = [[False] * (bb - yy) for _ in range(xx, aa)]\n",
    "        for xi, yi, ai, bi in rectangles:\n",
    "            for i in range(xi - xx, ai - xx):\n",
    "                if any(line[i][yi - yy: bi - yy]):\n",
    "                    return False\n",
    "                line[i][yi - yy: bi - yy] = [True] * (bi - yi)\n",
    "        return True\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        rectangles.sort(key=lambda x:[x[0], x[1]])\n",
    "        # check x[1]是不是最小\n",
    "        min_y = rectangles[0][1]\n",
    "        for r in rectangles:\n",
    "            if r[1] < min_y:\n",
    "                return False\n",
    "        \n",
    "        min_x= rectangles[0][0]\n",
    "\n",
    "        rectangles.sort(key=lambda x:[x[2], x[3]], reverse=True)\n",
    "        max_b = rectangles[0][3]\n",
    "        for r in rectangles:\n",
    "            if r[3] > max_b:\n",
    "                return False\n",
    "        max_a = rectangles[0][2]\n",
    "\n",
    "        sequare_sum = 0\n",
    "        for r in rectangles:\n",
    "            sequare_sum += (r[3]-r[1]) * (r[2]-r[0])\n",
    "\n",
    "        if sequare_sum != (max_b-min_y) * (max_a-min_x):\n",
    "            return False\n",
    "        \n",
    "        print(True)\n",
    "        points = []\n",
    "        cpoints = []\n",
    "        for r in rectangles:\n",
    "            xy = [r[0], r[1]]\n",
    "            ab = [r[2], r[3]]\n",
    "            xb = [r[0], r[3]]\n",
    "            ay = [r[2], r[1]]\n",
    "            for i in [xy, ab, xb, ay]:\n",
    "                if i not in points:\n",
    "                    points.append(i)\n",
    "                else:\n",
    "                    points.remove(i)\n",
    "\n",
    "        if len(points) != 4:\n",
    "            return False\n",
    "        print(points, min_x, min_y, max_a, max_b)\n",
    "        for i in [[min_x, min_y], [max_a, max_b], [min_x, max_b], [max_a, min_y]]:\n",
    "            if i not in points:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        #左下\n",
    "        x1,y1 = float('inf'), float('inf') \n",
    "        # 右上\n",
    "        x2,y2 = float('-inf'), float('-inf')\n",
    "\n",
    "        #顶点\n",
    "        points = set()\n",
    "\n",
    "        #实际面积\n",
    "        actual_area = 0\n",
    "        for xi,yi,ai,bi in rectangles:\n",
    "            # 获取期望矩形的 左下右上 左边\n",
    "            x1, y1 = min ( xi, x1), min(yi, y1)\n",
    "            x2, y2 = max( ai, x2),  max( bi, y2)\n",
    "\n",
    "            actual_area += (ai - xi) * ( bi - yi)\n",
    "            \n",
    "            # 小矩形的4个顶点\n",
    "            p1,p2 = (xi,bi), (ai,bi)\n",
    "            p3,p4 = ( ai, yi), (xi, yi)\n",
    "            #留下顶点 （奇数）\n",
    "            for p in (p1,p2,p3,p4):\n",
    "                if p in points:\n",
    "                    points.remove(p)\n",
    "                else:\n",
    "                    points.add(p)\n",
    "\n",
    "        # 判断期望矩形面积与实际矩形是否相同\n",
    "        expect_area = (x2-x1) * (y2-y1)\n",
    "        if actual_area != expect_area:\n",
    "            return False\n",
    "        \n",
    "        # 多余4个顶点 \n",
    "        if len(points) != 4:\n",
    "            return False\n",
    "        #左上\n",
    "        if (x1,y2) not in points:\n",
    "            return False\n",
    "        #右上\n",
    "        if ( x2, y2) not in points:\n",
    "            return False\n",
    "        #右下:\n",
    "        if (x2, y1) not in points:\n",
    "            return False\n",
    "        #左下\n",
    "        if (x1, y1) not in points:\n",
    "            return False\n",
    "        \n",
    "        #面积符合 顶点符合\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        x1, x2 = float(\"inf\"), -float(\"inf\")\n",
    "        y1, y2 = float(\"inf\"), -float(\"inf\")\n",
    "        points = set()\n",
    "        count = 0\n",
    "        for a1, b1, a2, b2 in rectangles:\n",
    "            x1 = min(x1, a1)\n",
    "            x2 = max(x2, a2)\n",
    "            y1 = min(y1, b1)\n",
    "            y2 = max(y2, b2)\n",
    "            count += (a2 - a1) * (b2 - b1)\n",
    "            p1, p2, p3, p4 = (a1, b1), (a1, b2), (a2, b1), (a2, b2)\n",
    "            for p in [p1, p2, p3, p4]:\n",
    "                if p in points: \n",
    "                    points.remove(p)\n",
    "                else:           \n",
    "                    points.add(p)\n",
    "        if count != (x2 - x1) * (y2 - y1) or len(points) != 4:\n",
    "            return False\n",
    "        if (x1, y1) not in points or (x1, y2) not in points or (x2, y1) not in points or (x2, y2) not in points:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\r\n",
    "        X1, Y1 = float('inf'), float('inf')\r\n",
    "        X2, Y2 = -float('inf'), -float('inf')\r\n",
    "        \r\n",
    "        points = set()\r\n",
    "        actual_area = 0\r\n",
    "        for x1, y1, x2, y2 in rectangles:\r\n",
    "            # 计算完美矩形的理论顶点坐标\r\n",
    "            X1, Y1 = min(X1, x1), min(Y1, y1)\r\n",
    "            X2, Y2 = max(X2, x2), max(Y2, y2)\r\n",
    "            # 累加小矩形的面积\r\n",
    "            actual_area += (x2 - x1) * (y2 - y1)\r\n",
    "            # 记录最终形成的图形中的顶点\r\n",
    "            p1, p2 = (x1, y1), (x1, y2)\r\n",
    "            p3, p4 = (x2, y1), (x2, y2)\r\n",
    "            for p in [p1, p2, p3, p4]:\r\n",
    "                if p in points: points.remove(p)\r\n",
    "                else:           points.add(p)\r\n",
    "        # 判断面积是否相同\r\n",
    "        expected_area = (X2 - X1) * (Y2 - Y1)\r\n",
    "        if actual_area != expected_area:\r\n",
    "            return False\r\n",
    "        # 判断最终留下的顶点个数是否为 4\r\n",
    "        if len(points) != 4:       return False\r\n",
    "        # 判断留下的 4 个顶点是否是完美矩形的顶点\r\n",
    "        if (X1, Y1) not in points: return False\r\n",
    "        if (X1, Y2) not in points: return False\r\n",
    "        if (X2, Y1) not in points: return False\r\n",
    "        if (X2, Y2) not in points: return False\r\n",
    "        # 面积和顶点都对应，说明矩形符合题意\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        X1, Y1 = float('inf'), float('inf')\n",
    "        X2, Y2 = -float('inf'), -float('inf')\n",
    "        \n",
    "        points = set()\n",
    "        actual_area = 0\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            # 计算完美矩形的理论顶点坐标\n",
    "            X1, Y1 = min(X1, x1), min(Y1, y1)\n",
    "            X2, Y2 = max(X2, x2), max(Y2, y2)\n",
    "            # 累加小矩形的面积\n",
    "            actual_area += (x2 - x1) * (y2 - y1)\n",
    "            # 记录最终形成的图形中的顶点\n",
    "            p1, p2 = (x1, y1), (x1, y2)\n",
    "            p3, p4 = (x2, y1), (x2, y2)\n",
    "\n",
    "            for p in [p1, p2, p3, p4]:\n",
    "                if p in points:\n",
    "                    points.remove(p)\n",
    "                else:\n",
    "                    points.add(p)\n",
    "\n",
    "\n",
    "        # 判断面积是否相同\n",
    "        expected_area = (X2 - X1) * (Y2 - Y1)\n",
    "        if actual_area != expected_area:\n",
    "            return False\n",
    "            \n",
    "        # 判断最终留下的顶点个数是否为 4\n",
    "        if len(points) != 4:\n",
    "            return False\n",
    "\n",
    "        # 判断留下的 4 个顶点是否是完美矩形的顶点\n",
    "        if (X1, Y1) not in points: return False\n",
    "        if (X1, Y2) not in points: return False\n",
    "        if (X2, Y1) not in points: return False\n",
    "        if (X2, Y2) not in points: return False\n",
    "        # 面积和顶点都对应，说明矩形符合题意\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        area=0\n",
    "        max_rec=[99999,99999,-99999,-99999]\n",
    "        s=set()\n",
    "        for i in rectangles:\n",
    "            if i[0]<max_rec[0]:\n",
    "                max_rec[0]=i[0]\n",
    "            if i[1]<max_rec[1]:\n",
    "                max_rec[1]=i[1]\n",
    "            if i[2]>max_rec[2]:\n",
    "                max_rec[2]=i[2]\n",
    "            if i[3]>max_rec[3]:\n",
    "                max_rec[3]=i[3]\n",
    "            area+=abs(i[2]-i[0])*abs(i[3]-i[1])\n",
    "            if (i[0],i[1]) in s:\n",
    "                s.remove((i[0],i[1]))\n",
    "            else:\n",
    "                s.add((i[0],i[1]))\n",
    "            if (i[2],i[1]) in s:\n",
    "                s.remove((i[2],i[1]))\n",
    "            else:\n",
    "                s.add((i[2],i[1]))\n",
    "            if (i[2],i[3]) in s:\n",
    "                s.remove((i[2],i[3]))\n",
    "            else:\n",
    "                s.add((i[2],i[3]))\n",
    "            if (i[0],i[3]) in s:\n",
    "                s.remove((i[0],i[3]))\n",
    "            else:\n",
    "                s.add((i[0],i[3]))\n",
    "        max_area=abs(max_rec[2]-max_rec[0])*abs(max_rec[3]-max_rec[1])\n",
    "        if (max_rec[0],max_rec[1]) in s:\n",
    "            s.remove((max_rec[0],max_rec[1]))\n",
    "        else:\n",
    "            return False\n",
    "        if (max_rec[2],max_rec[1]) in s:\n",
    "            s.remove((max_rec[2],max_rec[1]))\n",
    "        else:\n",
    "            return False\n",
    "        if (max_rec[2],max_rec[3]) in s:\n",
    "            s.remove((max_rec[2],max_rec[3]))\n",
    "        else:\n",
    "            return False\n",
    "        if (max_rec[0],max_rec[3]) in s:\n",
    "            s.remove((max_rec[0],max_rec[3]))\n",
    "        else:\n",
    "            return False\n",
    "        if max_area==area and len(s) == 0:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        area,minX,minY,maxX,maxY=0,rectangles[0][0],rectangles[0][1],rectangles[0][2],rectangles[0][3]\n",
    "        cnt=defaultdict(int)\n",
    "        for rect in rectangles:\n",
    "            x,y,a,b=rect[0],rect[1],rect[2],rect[3]\n",
    "            area+=(a-x)*(b-y)\n",
    "            minX=min(minX,x)\n",
    "            minY=min(minY,y)\n",
    "            maxX=max(maxX,a)\n",
    "            maxY=max(maxY,b)\n",
    "            cnt[(x,y)]+=1\n",
    "            cnt[(x,b)]+=1\n",
    "            cnt[(a,b)]+=1\n",
    "            cnt[(a,y)]+=1\n",
    "        if area!=(maxX-minX)*(maxY-minY) or cnt[(minX,minY)]!=1 or cnt[(maxX,minY)]!=1 or cnt[(maxX,maxY)]!=1 or cnt[(minX,maxY)]!=1:return False\n",
    "        del cnt[(minX,minY)],cnt[(maxX,minY)],cnt[(minX,maxY)],cnt[(maxX,maxY)]\n",
    "        return all(c==2 or c==4 for c in cnt.values())\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        area = 0 \n",
    "        max_a, max_b = -float(\"inf\"), -float('inf')\n",
    "        min_x, min_y = float(\"inf\"), float(\"inf\")\n",
    "        for x, y, a, b in rectangles:\n",
    "            max_a, max_b = max(a, max_a), max(b, max_b)\n",
    "            min_x, min_y = min(x, min_x), min(y, min_y)\n",
    "            area += (a - x) * (b - y)\n",
    "        if area != (max_a - min_x) * (max_b - min_y):\n",
    "            return False\n",
    "        end_points = {}\n",
    "        for x, y, a, b in rectangles:\n",
    "            for r, c in [(x, y), (x, b), (a, b), (a, y)]:\n",
    "                if (r, c) in end_points:\n",
    "                    end_points.pop((r,c))\n",
    "                else:\n",
    "                    end_points[(r, c)] = True\n",
    "        if not end_points:\n",
    "            return False\n",
    "        for (x, y), v in end_points.items():\n",
    "            if v and (x not in (max_a, min_x) or y not in (max_b, min_y)):\n",
    "                return False \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        # Area check\n",
    "        tx, ty, ta, tb = rectangles[0]\n",
    "        area_acc = 0\n",
    "        edges = []\n",
    "        for x, y, a, b in rectangles:\n",
    "            tx = min(tx, x)\n",
    "            ty = min(ty, y)\n",
    "            ta = max(ta, a)\n",
    "            tb = max(tb, b)\n",
    "            area_acc += (a - x) * (b - y)\n",
    "            edges.append((x, 1, y, b))\n",
    "            edges.append((a, -1, y, b))\n",
    "        if (ta - tx) * (tb - ty) != area_acc:\n",
    "            return False\n",
    "        # Collision check\n",
    "        edges.sort()\n",
    "        i = 0\n",
    "        cnt = defaultdict(int)\n",
    "        while i < len(edges):\n",
    "            point, direction, down, up = edges[i]\n",
    "            cnt[down] += direction\n",
    "            cnt[up] -= direction\n",
    "            if cnt[down] == 0:\n",
    "                del cnt[down]\n",
    "            if cnt[up] == 0:\n",
    "                del cnt[up]\n",
    "            while i + 1 < len(edges) and edges[i + 1][0] == point:\n",
    "                i += 1\n",
    "                _, cd, cdown, cup = edges[i]\n",
    "                cnt[cdown] += cd\n",
    "                cnt[cup] -= cd\n",
    "                if cnt[cdown] == 0:\n",
    "                    del cnt[cdown]\n",
    "                if cnt[cup] == 0:\n",
    "                    del cnt[cup]\n",
    "            if point == ta:\n",
    "                break\n",
    "            if not (len(cnt) == 2 and cnt[ty] == 1 and cnt[tb] == -1):\n",
    "                return False\n",
    "            i += 1\n",
    "        return True if len(cnt) == 0 else False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        #rectangles变为[x轴入点，x轴出点，y轴入点，y轴出点]\n",
    "        rectangles = [[_[0],_[2],_[1],_[3]] for _ in rectangles]\n",
    "        x_rectangles = defaultdict(list)\n",
    "        for _ in rectangles:\n",
    "            x_rectangles[(_[0],'in')].append(_)\n",
    "            x_rectangles[(_[1],'at')].append(_)\n",
    "        x_inout = list(x_rectangles.keys())\n",
    "        x_inout.sort()\n",
    "        # 除了首元素作为出点，尾元素作为入点，其他的点应该是出入匹配，且出点位于入点前\n",
    "        for x_out,x_in in zip(x_inout[1:-1:2],x_inout[2:-1:2]):\n",
    "            if x_in[0]!=x_out[0]:\n",
    "                return False\n",
    "\n",
    "        #按照x轴排序(出点在入点之前)，入点和出点分别标记，入点则要增加区间，出点则要减少区间\n",
    "        ymin = min([_[2] for _ in rectangles])\n",
    "        ymax = max([_[3] for _ in rectangles])\n",
    "        \n",
    "        rects_exist = [] #当前区间的矩形\n",
    "        cover_flag = True\n",
    "        for _ in x_inout:\n",
    "            if _[1] == 'in':\n",
    "                rects_exist.extend(x_rectangles[_])\n",
    "            else:\n",
    "                for rect in x_rectangles[_]:\n",
    "                    # 删除指定元素，这里将list改成集合可以降低复杂度\n",
    "                    rects_exist.remove(rect)\n",
    "            if _[1] == 'in':\n",
    "                # 判断rects_exist中的元素的y是否准确的覆盖[ymin,ymax]\n",
    "                rects_y = [(float('-inf'),ymin)]\n",
    "                for rect in rects_exist:\n",
    "                    rects_y.append((rect[2],rect[3]))\n",
    "                rects_y.append((ymax,float('inf')))\n",
    "                rects_y.sort()\n",
    "                for prev,now in zip(rects_y,rects_y[1:]):\n",
    "                    if prev[1]!=now[0]:\n",
    "                        cover_flag = False\n",
    "                        break\n",
    "                if not cover_flag:\n",
    "                    # cover_flag为False时\n",
    "                    break\n",
    "        return cover_flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        len_rectangles = len(rectangles)\n",
    "        if len_rectangles == 1:\n",
    "            return True\n",
    "\n",
    "        rectangles.sort()\n",
    "\n",
    "        rectangle = rectangles[0]\n",
    "        x_min = rectangle[0]\n",
    "        y_min = rectangle[1]\n",
    "        y_max = rectangle[3]\n",
    "        vertexs = [[rectangle[2], y_min], [rectangle[2], y_max]]\n",
    "        ind = 1\n",
    "        rectangle = rectangles[1]\n",
    "        while rectangle[0] == x_min:\n",
    "            if rectangle[1] != y_max:\n",
    "                return False\n",
    "\n",
    "            y_max = rectangle[3]\n",
    "            heapq.heappush(vertexs, [rectangle[2], rectangle[1]])\n",
    "            heapq.heappush(vertexs, [rectangle[2], rectangle[3]])\n",
    "            \n",
    "            ind += 1\n",
    "            if ind >= len_rectangles:\n",
    "                for i in range(1, len(vertexs)-1, 2):\n",
    "                    if vertexs[i][0] != vertexs[i+1][0]:\n",
    "                        return False\n",
    "                return True\n",
    "            rectangle = rectangles[ind]\n",
    "\n",
    "        for rectangle in rectangles[ind:]:\n",
    "            if rectangle[:2] != vertexs[0]:\n",
    "                return False\n",
    "\n",
    "            heapq.heappop(vertexs)\n",
    "            while rectangle[3] > vertexs[0][1]:\n",
    "                heapq.heappop(vertexs)\n",
    "                if len(vertexs) == 0 or rectangle[0] != vertexs[0][0]:\n",
    "                    return False\n",
    "            if rectangle[3] == vertexs[0][1]:\n",
    "                heapq.heappop(vertexs)\n",
    "                heapq.heappush(vertexs, [rectangle[2], rectangle[1]])\n",
    "                heapq.heappush(vertexs, [rectangle[2], rectangle[3]])\n",
    "            else:\n",
    "                heapq.heappush(vertexs, [rectangle[0], rectangle[3]])\n",
    "                heapq.heappush(vertexs, [rectangle[2], rectangle[1]])\n",
    "                heapq.heappush(vertexs, [rectangle[2], rectangle[3]])\n",
    "        \n",
    "        for i in range(len(vertexs)-1):\n",
    "            if vertexs[i][0] != vertexs[i+1][0]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        if not rectangles:\n",
    "            return False\n",
    "        n = len(rectangles)\n",
    "        # 解析数据，(x, y, a, b) -> (x, y, b, 1) ，(a, y, b, -1)\n",
    "        # 最后一位表示是矩形的左边缘还是右边缘（即扫描线的“上升”和“下降”）\n",
    "        rs = []\n",
    "        for rec in rectangles:\n",
    "            x, y, a, b = rec\n",
    "            rs.append([x, y, b, 1])\n",
    "            rs.append([a, y, b, -1])\n",
    "        rs.sort()\n",
    "        \n",
    "        l = r = 0\n",
    "        while r < len(rs):\n",
    "            l1 = [] # 记录“上升”的线段\n",
    "            l2 = [] # 记录“下降”的线段\n",
    "            while r < len(rs) and rs[r][0] == rs[l][0]:\n",
    "                r += 1\n",
    "            for i in range(l, r): # 遍历横坐标相同的线段\n",
    "                x, y1, y2, isUp = rs[i]\n",
    "                curl = l1 if isUp == 1 else l2 \n",
    "                if not curl:\n",
    "                    curl.append([y1, y2])\n",
    "                else:\n",
    "                    if curl[-1][1] > y1: # 有重叠\n",
    "                        return False \n",
    "                    elif curl[-1][1] == y1: # 能连接上，进行连接\n",
    "                        curl[-1][1] = y2 \n",
    "                    else: # 不能连接上，记录新的一段\n",
    "                        curl.append([y1, y2])\n",
    "            # 若处理的是最左边的边或最右边的边，此时应连成一个线段\n",
    "            if l == 0 or r == len(rs): \n",
    "                if len(l1) + len(l2) != 1:\n",
    "                    return False \n",
    "            else:\n",
    "                # 若处理的是中间的扫描线，此时上升的线段和下降的线段应完全相同才能正好重叠\n",
    "                if len(l1) != len(l2):\n",
    "                    return False \n",
    "                for i in range(len(l1)):\n",
    "                    if l1[i] != l2[i]:\n",
    "                        return False \n",
    "            l = r # 进入下一个横坐标的扫描\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\r\n",
    "        if not rectangles:\r\n",
    "            return False\r\n",
    "        n = len(rectangles)\r\n",
    "        # 解析数据，(x, y, a, b) -> (x, y, b, 1) ，(a, y, b, -1)\r\n",
    "        # 最后一位表示是矩形的左边缘还是右边缘（即扫描线的“上升”和“下降”）\r\n",
    "        rs = []\r\n",
    "        for rec in rectangles:\r\n",
    "            x, y, a, b = rec\r\n",
    "            rs.append([x, y, b, 1])\r\n",
    "            rs.append([a, y, b, -1])\r\n",
    "        rs.sort()\r\n",
    "        \r\n",
    "        l = r = 0\r\n",
    "        while r < len(rs):\r\n",
    "            l1 = [] # 记录“上升”的线段\r\n",
    "            l2 = [] # 记录“下降”的线段\r\n",
    "            while r < len(rs) and rs[r][0] == rs[l][0]:\r\n",
    "                r += 1\r\n",
    "            for i in range(l, r): # 遍历横坐标相同的线段\r\n",
    "                x, y1, y2, isUp = rs[i]\r\n",
    "                curl = l1 if isUp == 1 else l2 \r\n",
    "                if not curl:\r\n",
    "                    curl.append([y1, y2])\r\n",
    "                else:\r\n",
    "                    if curl[-1][1] > y1: # 有重叠\r\n",
    "                        return False \r\n",
    "                    elif curl[-1][1] == y1: # 能连接上，进行连接\r\n",
    "                        curl[-1][1] = y2 \r\n",
    "                    else: # 不能连接上，记录新的一段\r\n",
    "                        curl.append([y1, y2])\r\n",
    "            # 若处理的是最左边的边或最右边的边，此时应连成一个线段\r\n",
    "            if l == 0 or r == len(rs): \r\n",
    "                if len(l1) + len(l2) != 1:\r\n",
    "                    return False \r\n",
    "            else:\r\n",
    "                # 若处理的是中间的扫描线，此时上升的线段和下降的线段应完全相同才能正好重叠\r\n",
    "                if len(l1) != len(l2):\r\n",
    "                    return False \r\n",
    "                for i in range(len(l1)):\r\n",
    "                    if l1[i] != l2[i]:\r\n",
    "                        return False \r\n",
    "            l = r # 进入下一个横坐标的扫描\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        \"\"\"\n",
    "        将每个矩形看成两条竖直方向的边，用(x,y1,y2,flag)表示y1,y2分别代表竖边下上端点 flag是区分左边还是右边\n",
    "        完美矩形充要条件\n",
    "            每一条非边缘的竖边都成对出现（一条边左右重叠在一起）\n",
    "            边缘边则独立卫一条连续的竖边\n",
    "        \"\"\"\n",
    "        n = len(rectangles)\n",
    "        #解析数据\n",
    "        rs = []\n",
    "        for x1,y1,x2,y2 in rectangles:\n",
    "            rs.append([x1,y1,y2,1])#1是左边\n",
    "            rs.append([x2,y1,y2,-1])#-1是右边\n",
    "        rs.sort()\n",
    "        l = r = 0\n",
    "        while r<len(rs):\n",
    "            l1,l2 = [],[] #分别记录左右边\n",
    "            while r<len(rs) and rs[r][0]==rs[l][0]:#定位出横坐标相同的边\n",
    "                r += 1\n",
    "            for i in range(l,r):#遍历横坐标相同的边\n",
    "                x,y1,y2,flag = rs[i]\n",
    "                cur = l1 if flag==1 else l2\n",
    "                if not cur:\n",
    "                    cur.append([y1,y2])\n",
    "                else:\n",
    "                    if cur[-1][1]>y1: # 有重叠\n",
    "                        return False\n",
    "                    elif cur[-1][1]==y1: # 能连接上，进行连接\n",
    "                        cur[-1][1] = y2\n",
    "                    else:# 不能连接上，记录新的一段 因为可能在之前就形成了一个中间矩形\n",
    "                        cur.append([y1,y2])\n",
    "            # 若处理的是最左边的边或最右边的边，此时应连成一个线段\n",
    "            if l==0 or r==len(rs):\n",
    "                if len(l1)+len(l2)!=1:\n",
    "                    return False\n",
    "            else: # 若处理的是中间的扫描线，此时上升的线段和下降的线段应完全相同才能正好重叠\n",
    "                if len(l1) != len(l2):\n",
    "                    return False \n",
    "                for i in range(len(l1)):\n",
    "                    if l1[i] != l2[i]:\n",
    "                        return False \n",
    "            l = r # 进入下一个横坐标的扫描\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        n = len(rectangles)\n",
    "        rs = []\n",
    "        for rec in rectangles:\n",
    "            a, b, c, d = rec\n",
    "            rs.append([a, b, d, 1])\n",
    "            rs.append([c, b, d, -1])\n",
    "        rs.sort()\n",
    "        l = 0\n",
    "        r = 0\n",
    "        while r < len(rs):\n",
    "            l1 = []\n",
    "            l2 = []\n",
    "            while r < len(rs) and rs[r][0] == rs[l][0]:\n",
    "                r += 1\n",
    "            for i in range(l, r):\n",
    "                x, y1, y2, is_up = rs[i]\n",
    "                curl = l1 if is_up == 1 else l2\n",
    "                if not curl:\n",
    "                    curl.append([y1, y2])\n",
    "                else:\n",
    "                    if curl[-1][1] > y1:\n",
    "                        return False\n",
    "                    elif curl[-1][1] == y1:\n",
    "                        curl[-1][1] = y2\n",
    "                    else:\n",
    "                        curl.append([y1, y2])\n",
    "            if l == 0 or r == len(rs):\n",
    "                if len(l1) + len(l2) != 1:\n",
    "                    return False\n",
    "            else:\n",
    "                if len(l1) != len(l2):\n",
    "                    return False\n",
    "                for i in range(len(l1)):\n",
    "                    if l1[i] != l2[i]:\n",
    "                        return False\n",
    "            l = r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        line=[]\n",
    "        for l in rectangles:\n",
    "            line.append([l[0],l[1],l[3],'l'])\n",
    "            line.append([l[2],l[1],l[3],'r'])\n",
    "        line.sort()\n",
    "        ll=line[0][0]\n",
    "        rr=line[-1][0]\n",
    "        templ=[]\n",
    "        tempr=[] \n",
    "        x_temp=line[0][0]\n",
    "        temp_edgel=[]\n",
    "        temp_edger=[]\n",
    "        for [x,y1,y2,direction] in line:  \n",
    "            if x_temp!=x and x_temp!=ll:\n",
    "                if len(templ)!=len(tempr):return False\n",
    "                for m,n in zip(templ,tempr):\n",
    "                    if m!=n:return False\n",
    "                templ=[]\n",
    "                tempr=[]\n",
    "            x_temp=x\n",
    "            if x==ll:\n",
    "                if not temp_edgel: \n",
    "                    temp_edgel=[y1,y2]\n",
    "                elif temp_edgel[1]!=y1:return False\n",
    "                else:temp_edgel[1]=y2\n",
    "            elif x==rr:\n",
    "                if not temp_edger: temp_edger=[y1,y2]\n",
    "                elif temp_edger[1]!=y1:return False\n",
    "                else:temp_edger[1]=y2\n",
    "                \n",
    "            elif direction=='r':\n",
    "                if not tempr: tempr.append([y1,y2])\n",
    "                elif tempr[-1][1]>y1:return False\n",
    "                elif tempr[-1][1]==y1:tempr[-1][1]=y2\n",
    "                else:tempr.append([y1,y2]) \n",
    "            \n",
    "            else:\n",
    "                if not templ: templ.append([y1,y2])\n",
    "                elif templ[-1][1]>y1:return False\n",
    "                elif templ[-1][1]==y1:templ[-1][1]=y2\n",
    "                else:templ.append([y1,y2]) \n",
    "        if temp_edgel!=temp_edger:return False\n",
    "        return True\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles):\n",
    "        if len(rectangles) <= 1:\n",
    "            return True\n",
    "\n",
    "        d = {}\n",
    "        s = 0\n",
    "        minx, miny, maxx, maxy = float(\"inf\"),float(\"inf\"),float(\"-inf\"),float(\"-inf\")\n",
    "        for r in rectangles:\n",
    "            cor1 = \"{}-{}\".format(r[0],r[1])\n",
    "            cor2 = \"{}-{}\".format(r[2],r[3])\n",
    "            cor3 = \"{}-{}\".format(r[2],r[1])\n",
    "            cor4 = \"{}-{}\".format(r[0],r[3])\n",
    "            d[cor1] = d.get(cor1, 0) + 1\n",
    "            d[cor2] = d.get(cor2, 0) + 1\n",
    "            d[cor3] = d.get(cor3, 0) + 1\n",
    "            d[cor4] = d.get(cor4, 0) + 1\n",
    "            minx = min(r[0], minx)\n",
    "            miny = min(r[1], miny)\n",
    "            maxx = max(r[2], maxx)\n",
    "            maxy = max(r[3], maxy)\n",
    "            s += (r[2] - r[0]) * (r[3]-r[1])\n",
    "        \n",
    "        if s != (maxx-minx) * (maxy-miny):\n",
    "            return False\n",
    "\n",
    "        for x in [minx, maxx]:\n",
    "            for y in [miny, maxy]:\n",
    "                point = \"{}-{}\".format(x, y)\n",
    "                if d.get(point) != 1:\n",
    "                    return False\n",
    "                del d[point]\n",
    "    \n",
    "        return all (v==2 or v==4 for v in d.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        x_1, x_2 = float('inf'), -float('inf')\n",
    "        y_1, y_2 = float('inf'), -float('inf')\n",
    "\n",
    "        area = 0\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            x_1, x_2 = min(x1, x_1), max(x2, x_2)\n",
    "            y_1, y_2 = min(y1, y_1), max(y2, y_2)\n",
    "            area += (x2 - x1) * (y2 - y1)\n",
    "        \n",
    "        cover_area = (x_2 - x_1) * (y_2 - y_1)\n",
    "        if cover_area != area:\n",
    "            return False\n",
    "\n",
    "        points = collections.defaultdict(int)\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            p1, p2, p3, p4 = (x1, y1), (x2, y1), (x1, y2), (x2, y2)\n",
    "            points[p1] += 1\n",
    "            points[p2] += 1\n",
    "            points[p3] += 1\n",
    "            points[p4] += 1\n",
    "        points_remain = [p for p, v in points.items() if v%2]\n",
    "\n",
    "        if len(points_remain) != 4:\n",
    "            return False\n",
    "            \n",
    "        if (x_1, y_1) not in points_remain: return False\n",
    "        if (x_1, y_2) not in points_remain: return False\n",
    "        if (x_2, y_1) not in points_remain: return False\n",
    "        if (x_2, y_2) not in points_remain: return False\n",
    "\n",
    "        return True\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        n = len(rectangles)\n",
    "        x_idx, y_idx = [], []\n",
    "        min_y, max_y = math.inf, 0\n",
    "        for i, (x, y, a, b) in enumerate(rectangles):\n",
    "            x_idx.append((x, i, 0))\n",
    "            x_idx.append((a, i, 1))\n",
    "            y_idx.append((y, b, i))\n",
    "            min_y, max_y = min(min_y, y), max(max_y, b)\n",
    "            \n",
    "        max_width = max_y - min_y\n",
    "        x_idx.sort()\n",
    "        y_idx.sort()\n",
    "        \n",
    "        i, m = 0, n << 1\n",
    "        active = [False] * n \n",
    "        while i < m:\n",
    "            x = x_idx[i][0]\n",
    "            while i < m and x_idx[i][0] == x:\n",
    "                active[x_idx[i][1]] = x_idx[i][2] == 0\n",
    "                i += 1\n",
    "            if i == m:\n",
    "                break\n",
    "\n",
    "            y = min_y\n",
    "            for y1, y2, j in y_idx:\n",
    "                if active[j]:\n",
    "                    if y == y1:\n",
    "                        y = y2 \n",
    "                    else:\n",
    "                        return False \n",
    "            if y < max_y:\n",
    "                return False\n",
    "        return True\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles):\n",
    "        \"\"\"\n",
    "        给你一个数组 rectangles ，其中 rectangles[i] = [xi, yi, ai, bi] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (xi, yi) ，右上顶点是 (ai, bi) 。\n",
    "        如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。\n",
    "        \"\"\"\n",
    "        if len(rectangles) <= 1:\n",
    "            return True\n",
    "\n",
    "        if not self.is_area_equal(rectangles):\n",
    "            return False\n",
    "        \n",
    "        d = {}\n",
    "        minx, miny, maxx, maxy = float(\"inf\"),float(\"inf\"),float(\"-inf\"),float(\"-inf\")\n",
    "        for r in rectangles:\n",
    "            cor1 = \"{}-{}\".format(r[0],r[1])\n",
    "            cor2 = \"{}-{}\".format(r[2],r[3])\n",
    "            cor3 = \"{}-{}\".format(r[2],r[1])\n",
    "            cor4 = \"{}-{}\".format(r[0],r[3])\n",
    "            d[cor1] = d.get(cor1, 0) + 1\n",
    "            d[cor2] = d.get(cor2, 0) + 1\n",
    "            d[cor3] = d.get(cor3, 0) + 1\n",
    "            d[cor4] = d.get(cor4, 0) + 1\n",
    "            minx = min(r[0], minx)\n",
    "            miny = min(r[1], miny)\n",
    "            maxx = max(r[2], maxx)\n",
    "            maxy = max(r[3], maxy)\n",
    "\n",
    "        for x in [minx, maxx]:\n",
    "            for y in [miny, maxy]:\n",
    "                point = \"{}-{}\".format(x, y)\n",
    "                if d.get(point) != 1:\n",
    "                    return False\n",
    "                del d[point]\n",
    "    \n",
    "        return all (v==2 or v==4 for v in d.values())\n",
    "\n",
    "\n",
    "    def is_area_equal(self, rect):\n",
    "        s = 0\n",
    "        minx, miny, maxx, maxy = float(\"inf\"),float(\"inf\"),float(\"-inf\"),float(\"-inf\")\n",
    "        for r in rect:\n",
    "            minx = min(r[0], minx)\n",
    "            miny = min(r[1], miny)\n",
    "            maxx = max(r[2], maxx)\n",
    "            maxy = max(r[3], maxy)\n",
    "            s += (r[2] - r[0]) * (r[3]-r[1])\n",
    "\n",
    "        return s == (maxx-minx) * (maxy-miny)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        d = defaultdict(list)\n",
    "        for x,y,a,b in rectangles:\n",
    "            d[x].append((0,y,b))\n",
    "            d[a].append((1,y,b))\n",
    "        def gen(A):\n",
    "            res = []\n",
    "            for x,y in sorted(A):\n",
    "                if not res or x>res[-1][1]:\n",
    "                    res.append([x,y])\n",
    "                elif x==res[-1][1]:\n",
    "                    res[-1][1] = y\n",
    "                else:\n",
    "                    return []\n",
    "            return res\n",
    "        A = sorted(d)\n",
    "        first = [(y1,y2) for _,y1,y2 in d[A[0]]]\n",
    "        if len(gen(first))!=1:\n",
    "            return False\n",
    "        for x in A[1:-1]:\n",
    "            B = [[],[]]\n",
    "            for i,y1,y2 in d[x]:\n",
    "                B[i].append((y1,y2))\n",
    "            if not (gen(B[0])==gen(B[1])!=[]):\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start \n",
    "        self.end = end \n",
    "        self.cnt = 0\n",
    "        self.left = None \n",
    "        self.right = None \n",
    "        self.lazy = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, X):\n",
    "        n = len(X)\n",
    "        if not n:\n",
    "            return \n",
    "        self.root = self.build(0, n - 1)\n",
    "    \n",
    "    def build(self, start, end):\n",
    "        if start > end:\n",
    "            return \n",
    "        root = Node(start, end)\n",
    "        if start == end:\n",
    "            return root \n",
    "        mid = (start + end) // 2 \n",
    "        root.left = self.build(start, mid)\n",
    "        root.right = self.build(mid + 1, end)\n",
    "        return root \n",
    "    \n",
    "    def update(self, root, i, j, val):\n",
    "        if root.start == i and root.end == j:\n",
    "            root.lazy += val\n",
    "            root.cnt += val \n",
    "            return \n",
    "        mid = (root.start + root.end) // 2 \n",
    "        self.push_down(root)\n",
    "        if i <= mid:\n",
    "            self.update(root.left, i, min(j, mid), val) \n",
    "        if j > mid:\n",
    "            self.update(root.right, max(i, mid + 1), j, val)\n",
    "        self.push_up(root)\n",
    "        return root \n",
    "    \n",
    "    def push_down(self, root):\n",
    "        if root.lazy:\n",
    "            if root.left:\n",
    "                root.left.lazy += root.lazy \n",
    "                root.left.cnt += root.lazy \n",
    "            if root.right:\n",
    "                root.right.lazy += root.lazy \n",
    "                root.right.cnt += root.lazy \n",
    "            root.lazy = 0 \n",
    "    \n",
    "    def push_up(self, root):\n",
    "        root.cnt = max(root.left.cnt, root.right.cnt)\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        left, right, up, down = float('inf'), - float('inf'), float('inf'), - float('inf')\n",
    "        X = set()\n",
    "        event = []\n",
    "        area = 0\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            X.add(x1)\n",
    "            X.add(x2)\n",
    "            event.append([y1, 1, x1, x2])\n",
    "            event.append([y2, - 1, x1, x2])\n",
    "            left = min(left, y1)\n",
    "            right = max(right, y2)\n",
    "            up = min(up, x1)\n",
    "            down = max(down, x2)\n",
    "            area += (y1 - y2) * (x1 - x2)\n",
    "        if area != (left - right) * (up - down):\n",
    "            return False \n",
    "        event.sort()\n",
    "        X = sorted(X)\n",
    "        sg = SegmentTree(X)\n",
    "        Xi = {x : i for i, x in enumerate(X)}\n",
    "        for y, val, x1, x2 in event:\n",
    "            sg.update(sg.root, Xi[x1], Xi[x2] - 1, val)\n",
    "            if sg.root.cnt > 1:\n",
    "                return False \n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        min_x = float('inf')\n",
    "        min_y = float('inf')\n",
    "        max_a = float('-inf')\n",
    "        max_b = float('-inf')\n",
    "        sum_area = 0\n",
    "        points = []\n",
    "        for x,y,a,b in rectangles:\n",
    "            for i in [x,a]:\n",
    "                for j in [y,b]:\n",
    "                    # if (i,j) in points:\n",
    "                    #     points.remove((i,j))\n",
    "                    # else:\n",
    "                    points.append((i,j))\n",
    "            sum_area += (a-x) * (b-y)\n",
    "            min_x = min(min_x,x)\n",
    "            min_y = min(min_y,y)\n",
    "            max_a = max(max_a,a)\n",
    "            max_b = max(max_b,b)\n",
    "        m = max_a - min_x\n",
    "        n = max_b - min_y\n",
    "        \n",
    "        if m*n != sum_area: \n",
    "            return False\n",
    "        res = []\n",
    "        for point, cnt in collections.Counter(points).items():\n",
    "            if cnt == 1:\n",
    "                res.append(point)\n",
    "            elif cnt % 2 == 1:\n",
    "                return False\n",
    "        if len(res) == 4 and (min_x, min_y) in res and (min_x, max_b) in res and (max_a, min_y) in res and (max_a, max_b) in res:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "        self.left = None \n",
    "        self.right = None \n",
    "        self.lazy = 0\n",
    "        self.cnt = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, X):\n",
    "        n = len(X)\n",
    "        if not n:\n",
    "            return \n",
    "        self.root = Node(0, n - 1)\n",
    "    \n",
    "    def update(self, root, i, j, val):\n",
    "        if root.start == i and root.end == j:\n",
    "            root.lazy += val \n",
    "            root.cnt += val \n",
    "            return \n",
    "        mid = root.start + (root.end - root.start) // 2\n",
    "        if not root.left:\n",
    "            root.left = Node(root.start, mid)\n",
    "        if not root.right:\n",
    "            root.right = Node(mid + 1, root.end)\n",
    "        self.push_down(root)\n",
    "        if i <= mid:\n",
    "            self.update(root.left, i, min(j, mid), val)\n",
    "        if j > mid:\n",
    "            self.update(root.right, max(i, mid + 1), j, val)\n",
    "        self.push_up(root)\n",
    "    \n",
    "    def push_down(self, root):\n",
    "        if root.lazy:\n",
    "            root.left.cnt += root.lazy\n",
    "            root.left.lazy = root.lazy\n",
    "            root.right.cnt += root.lazy\n",
    "            root.right.lazy = root.lazy\n",
    "        root.lazy = 0\n",
    "    \n",
    "    def push_up(self, root):\n",
    "        root.cnt = max(root.left.cnt, root.right.cnt)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        X = set()\n",
    "        event = []\n",
    "        area = 0\n",
    "        left, right, up, down = float('inf'), - float('inf'), float('inf'), - float('inf')\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            X.add(x1)\n",
    "            X.add(x2)\n",
    "            event.append([y1, 1, x1, x2])\n",
    "            event.append([y2, - 1, x1, x2])\n",
    "            left = min(left, y1)\n",
    "            right = max(right, y2)\n",
    "            up = min(up, x1)\n",
    "            down = max(down, x2)\n",
    "            area += (y2 - y1) * (x2 - x1)\n",
    "        if area != (left - right) * (up - down):\n",
    "            return False \n",
    "        event.sort()\n",
    "        X = sorted(X)\n",
    "        sg = SegmentTree(X)\n",
    "        Xi = {x : i for i, x in enumerate(X)}\n",
    "        for y, val, x1, x2 in event:\n",
    "            sg.update(sg.root, Xi[x1], Xi[x2] - 1, val)\n",
    "            if sg.root.cnt > 1:\n",
    "                return False \n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "        self.left = None \n",
    "        self.right = None \n",
    "        self.lazy = 0\n",
    "        self.cnt = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, X):\n",
    "        n = len(X)\n",
    "        if not n:\n",
    "            return \n",
    "        self.root = Node(0, n - 1)\n",
    "    \n",
    "    def update(self, root, i, j, val):\n",
    "        if root.start == i and root.end == j:\n",
    "            root.lazy += val \n",
    "            root.cnt += val \n",
    "            return \n",
    "        mid = root.start + (root.end - root.start) // 2\n",
    "        if not root.left:\n",
    "            root.left = Node(root.start, mid)\n",
    "        if not root.right:\n",
    "            root.right = Node(mid + 1, root.end)\n",
    "        self.push_down(root)\n",
    "        if i <= mid:\n",
    "            self.update(root.left, i, min(j, mid), val)\n",
    "        if j > mid:\n",
    "            self.update(root.right, max(i, mid + 1), j, val)\n",
    "        self.push_up(root)\n",
    "    \n",
    "    def push_down(self, root):\n",
    "        if root.lazy:\n",
    "            root.left.cnt += root.lazy\n",
    "            root.left.lazy = root.lazy\n",
    "            root.right.cnt += root.lazy\n",
    "            root.right.lazy = root.lazy\n",
    "        root.lazy = 0\n",
    "    \n",
    "    def push_up(self, root):\n",
    "        root.cnt = max(root.left.cnt, root.right.cnt)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        X = set()\n",
    "        event = []\n",
    "        area = 0\n",
    "        left, right, up, down = float('inf'), - float('inf'), float('inf'), - float('inf')\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            X.add(x1)\n",
    "            X.add(x2)\n",
    "            event.append([y1, 1, x1, x2])\n",
    "            event.append([y2, - 1, x1, x2])\n",
    "            left = min(left, y1)\n",
    "            right = max(right, y2)\n",
    "            up = min(up, x1)\n",
    "            down = max(down, x2)\n",
    "            area += (y2 - y1) * (x2 - x1)\n",
    "        if area != (left - right) * (up - down):\n",
    "            return False \n",
    "        event.sort()\n",
    "        X = sorted(X)\n",
    "        sg = SegmentTree(X)\n",
    "        Xi = {x : i for i, x in enumerate(X)}\n",
    "        for y, val, x1, x2 in event:\n",
    "            sg.update(sg.root, Xi[x1], Xi[x2] - 1, val)\n",
    "            if sg.root.cnt > 1:\n",
    "                return False \n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        area, minX, minY, maxX, maxY = 0, inf, inf, -inf, -inf\n",
    "        cnt = defaultdict(int)\n",
    "        for rect in rectangles:\n",
    "            x, y, a, b = rect[0], rect[1], rect[2], rect[3]\n",
    "            area += (a - x) * (b - y)\n",
    "\n",
    "            minX = min(minX, x)\n",
    "            minY = min(minY, y)\n",
    "            maxX = max(maxX, a)\n",
    "            maxY = max(maxY, b)\n",
    "\n",
    "            cnt[(x, y)] += 1\n",
    "            cnt[(x, b)] += 1\n",
    "            cnt[(a, y)] += 1\n",
    "            cnt[(a, b)] += 1\n",
    "\n",
    "        # 面积符合要求但可能有缺口，例如示例2再补一个3*1的矩形与第一列重叠\n",
    "        # 这要求四个角的cnt必须为1，其余角的cnt必须为2或4，才可以保证不重叠\n",
    "        if area != (maxX - minX) * (maxY - minY) or cnt[(minX, minY)] != 1 or cnt[(minX, maxY)] != 1 or cnt[(maxX, minY)] != 1 or cnt[(maxX, maxY)] != 1:\n",
    "            return False\n",
    "\n",
    "        del cnt[(minX, minY)], cnt[(minX, maxY)], cnt[(maxX, minY)], cnt[(maxX, maxY)]\n",
    "\n",
    "        return all(c == 2 or c == 4 for c in cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        x, y, a, b, s = inf, inf, -inf, -inf, 0\n",
    "        cnts = Counter()\n",
    "        for x_, y_, a_, b_ in rectangles:\n",
    "            x, y, a, b = min(x, x_), min(y, y_), max(a, a_), max(b, b_)\n",
    "            s += (a_ - x_) * (b_ - y_)\n",
    "            cnts[(x_, y_)] += 1\n",
    "            cnts[(a_, b_)] += 1\n",
    "            cnts[(x_, b_)] += 1\n",
    "            cnts[(a_, y_)] += 1\n",
    "        if s != (a - x) * (b - y):\n",
    "            return False\n",
    "        ps = {(x, y), (x, b), (a, y), (a, b)}\n",
    "        for p in ps:\n",
    "            if cnts[p] != 1:\n",
    "                return False\n",
    "        for i, v in cnts.items():\n",
    "            if v > 4 or (i not in ps and v % 2):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        area = 0\n",
    "        min_x = min_y = float('inf')\n",
    "        max_x = max_y = float('-inf')\n",
    "        # dict储存每个顶点的出现次数\n",
    "        d_map = defaultdict(int)\n",
    "        for rectangle in rectangles:\n",
    "            x1 = rectangle[0]\n",
    "            x2 = rectangle[2]\n",
    "            y1 = rectangle[1]\n",
    "            y2 = rectangle[3]\n",
    "            area += (x2 - x1) * (y2 - y1)\n",
    "            # 单个矩形左下顶点\n",
    "            d_map[(x1, y1)] += 1\n",
    "            # 单个矩形左上顶点\n",
    "            d_map[(x1, y2)] += 1\n",
    "            # 单个矩形右下顶点\n",
    "            d_map[(x2, y1)] += 1\n",
    "            # 单个矩形右上顶点\n",
    "            d_map[(x2, y2)] += 1\n",
    "            # 记录最小和最大的x和y，用来确定最后完美矩形的四个顶点\n",
    "            min_x = min(min_x, x1)\n",
    "            min_y = min(min_y, y1)\n",
    "            max_x = max(max_x, x2)\n",
    "            max_y = max(max_y, y2)\n",
    "        # 两个面积是否相等\n",
    "        if (max_x - min_x) * (max_y - min_y) != area:\n",
    "            return False\n",
    "        # 四个顶点\n",
    "        ds = [(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)]\n",
    "        # 面积相等的情况通过顶点出现次数判断是否有相交矩形\n",
    "        for k, v in d_map.items():\n",
    "            # 非四个顶点出现次数\n",
    "            if k not in ds and v not in [2, 4]:\n",
    "                return False\n",
    "            # 四个顶点出现次数\n",
    "            if k in ds and v != 1:\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        min_x, min_y, max_x, max_y = rectangles[0]\n",
    "        total_area = 0\n",
    "        vertex_freq = {}\n",
    "        for x1, y1, x2, y2 in rectangles:\n",
    "            total_area += (x2 - x1) * (y2 - y1)\n",
    "            min_x = min(min_x, x1)\n",
    "            min_y = min(min_y, y1)\n",
    "            max_x = max(max_x, x2)\n",
    "            max_y = max(max_y, y2)\n",
    "            for key in [(x1, y1), (x1, y2), (x2, y1), (x2, y2)]:\n",
    "                if key not in vertex_freq:\n",
    "                    vertex_freq[key] = 1\n",
    "                else:\n",
    "                    vertex_freq[key] += 1\n",
    "        if (max_y - min_y) * (max_x - min_x) != total_area:\n",
    "            return False\n",
    "        vertex_set = set(\n",
    "            [(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)]\n",
    "        )\n",
    "        for key in vertex_set:\n",
    "            if key not in vertex_freq or vertex_freq[key] != 1:\n",
    "                return False\n",
    "        for key in vertex_freq.keys():\n",
    "            if (\n",
    "                key not in vertex_set\n",
    "                and vertex_freq[key] != 2\n",
    "                and vertex_freq[key] != 4\n",
    "            ):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        exp_area = 0\n",
    "        point_dict = {}\n",
    "        for rectangle in rectangles:\n",
    "            if rectangles.count(rectangle) != 1:\n",
    "                return False\n",
    "            exp_area += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1])\n",
    "            p1 = (rectangle[0], rectangle[1])\n",
    "            p2 = (rectangle[0], rectangle[3])\n",
    "            p3 = (rectangle[2], rectangle[1])\n",
    "            p4 = (rectangle[2], rectangle[3])\n",
    "            point_dict[p1] = point_dict.get(p1, 0) + 1\n",
    "            point_dict[p2] = point_dict.get(p2, 0) + 1\n",
    "            point_dict[p3] = point_dict.get(p3, 0) + 1\n",
    "            point_dict[p4] = point_dict.get(p4, 0) + 1\n",
    "        single_points = []\n",
    "        for key, value in point_dict.items():\n",
    "            if value == 1:\n",
    "                single_points.append(key)\n",
    "        if len(single_points) != 4:\n",
    "            return False\n",
    "        single_points.sort(key=lambda x: x[0])\n",
    "        # single_points = sorted(single_points, key=lambda x: x[0])\n",
    "        rst_area = abs((single_points[1][1] - single_points[0][1]) * (single_points[2][0] - single_points[0][0]))\n",
    "        if rst_area != exp_area:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "      area, minX, minY, maxX, maxY = 0, rectangles[0][0], rectangles[0][1], rectangles[0][2], rectangles[0][3]\n",
    "      cnt = Counter()\n",
    "      for rec in rectangles:\n",
    "        x, y, a, b = rec[0], rec[1], rec[2], rec[3]\n",
    "        area += (a - x) * (b - y)\n",
    "\n",
    "        minX = min(minX, x)\n",
    "        minY = min(minY, y)\n",
    "        maxX = max(maxX, a)\n",
    "        maxY = max(maxY, b)\n",
    "\n",
    "        cnt[(x, y)] += 1\n",
    "        cnt[(x, b)] += 1\n",
    "        cnt[(a, y)] += 1\n",
    "        cnt[(a, b)] += 1\n",
    "      if area != (maxX - minX) * (maxY - minY) or \\\n",
    "      cnt[(minX, minY)] != 1 or cnt[(minX, maxY)] != 1 or \\\n",
    "      cnt[(maxX, minY)] != 1 or cnt[(maxX, maxY)] != 1:\n",
    "          return False\n",
    "\n",
    "      del cnt[(minX, minY)], cnt[(minX, maxY)], cnt[(maxX, minY)], cnt[(maxX, maxY)]\n",
    "\n",
    "      return all(c == 2 or c == 4 for c in cnt.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        area, minX, minY, maxX, maxY = 0, rectangles[0][0], rectangles[0][1], rectangles[0][2], rectangles[0][3]\n",
    "        cnt = defaultdict(int)\n",
    "        for rect in rectangles:\n",
    "            x, y, a, b = rect[0], rect[1], rect[2], rect[3]\n",
    "            area += (a - x) * (b - y)\n",
    "            minX = min(minX, x)\n",
    "            minY = min(minY, y)\n",
    "            maxX = max(maxX, a)\n",
    "            maxY = max(maxY, b)\n",
    "\n",
    "            cnt[(x, y)] += 1\n",
    "            cnt[(x, b)] += 1\n",
    "            cnt[(a, y)] += 1\n",
    "            cnt[(a, b)] += 1\n",
    "\n",
    "        if area != (maxX - minX) * (maxY - minY) or cnt[(minX, minY)] != 1 or cnt[(minX, maxY)] != 1 or cnt[(maxX, minY)] != 1 or cnt[(maxX, maxY)] != 1:\n",
    "            return False\n",
    "\n",
    "        del cnt[(minX, minY)], cnt[(minX, maxY)], cnt[(maxX, minY)], cnt[(maxX, maxY)]\n",
    "\n",
    "        return all(c == 2 or c == 4 for c in cnt.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        rect = rectangles[0]\n",
    "        minX, minY, maxX, maxY = rect[0], rect[1], rect[2], rect[3]\n",
    "\n",
    "        area = 0\n",
    "        cnt_dict = defaultdict(int)\n",
    "        for rect in rectangles:\n",
    "            x, y, a, b = rect\n",
    "            area += (a - x) * (b - y)\n",
    "\n",
    "            minX = min(minX, x)\n",
    "            maxX = max(maxX, a)\n",
    "            minY = min(minY, y)\n",
    "            maxY = max(maxY, b)\n",
    "\n",
    "            cnt_dict[(x, y)] += 1\n",
    "            cnt_dict[(x, b)] += 1\n",
    "            cnt_dict[(a, y)] += 1\n",
    "            cnt_dict[(a, b)] += 1\n",
    "        \n",
    "        if (maxX - minX) * (maxY - minY) != area or cnt_dict[(minX, minY)] != 1 or cnt_dict[(minX, maxY)] != 1 or cnt_dict[(maxX, maxY)] != 1 or cnt_dict[(maxX, minY)] != 1:\n",
    "            return False\n",
    "        \n",
    "        del cnt_dict[(minX, minY)], cnt_dict[(minX, maxY)], cnt_dict[(maxX, maxY)], cnt_dict[(maxX, minY)]\n",
    "        for value in cnt_dict.values():\n",
    "            if not (value == 2 or value == 4):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        # 扫描线解法，所有的矩形都拆解为垂直2条线段，合并线段\n",
    "        # 左右边缘线段必须只有一段并且长度为最终矩形的高\n",
    "        # 中间线段必须有两端，且长度相等\n",
    "        mx_x, mx_y, mn_x, mn_y = -10**10, -10**10, 10**10, 10**10\n",
    "        seg_l, seg_r = defaultdict(dict), defaultdict(dict)  # y1-y2 矩形左右垂直线段\n",
    "        area = 0\n",
    "        for x, y, a, b in rectangles:\n",
    "            mx_x, mx_y = max(mx_x, a), max(mx_y, b)\n",
    "            mn_x, mn_y = min(mn_x, x), min(mn_y, y)\n",
    "            seg_l[x][y] = b\n",
    "            seg_r[a][y] = b\n",
    "            area += (a - x) * (b - y)\n",
    "        if area != (mx_x - mn_x) * (mx_y - mn_y): return False  # 面积不匹配\n",
    "        # 校验左外垂直线段\n",
    "        d = seg_l.pop(mn_x, None)\n",
    "        e = self.merge(d, mn_y)\n",
    "        if e != mx_y or d: return False\n",
    "        # 校验右外垂直线段\n",
    "        d = seg_r.pop(mx_x, None)\n",
    "        e = self.merge(d, mn_y)\n",
    "        if e != mx_y or d: return False\n",
    "        # 校验中间线段\n",
    "        for k, seg_d_l in seg_l.items():\n",
    "            seg_d_r = seg_r.get(k, None)\n",
    "            while seg_d_l:\n",
    "                start = min(seg_d_l.keys())\n",
    "                e_l = self.merge(seg_d_l, start)\n",
    "                e_r = self.merge(seg_d_r, start)\n",
    "                if e_l != e_r:\n",
    "                    return False  # 左垂直线段没有找到匹配的右垂直线段\n",
    "        return True\n",
    "        \n",
    "    def merge(self, seg_dic: dict | None, s):\n",
    "        if seg_dic is None: return None\n",
    "        e = s\n",
    "        while seg_dic and e is not None:\n",
    "            e = seg_dic.pop(e, None)\n",
    "        return e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        x1,y1,x2,y2=rectangles[0]\n",
    "        total=0\n",
    "        bian=defaultdict(int)\n",
    "        for r in rectangles:\n",
    "            x,y,a,b=r\n",
    "            x1,y1,x2,y2=min(x1,x),min(y1,y),max(x2,a),max(y2,b)\n",
    "            total+=(a-x)*(b-y)\n",
    "            bian[(x,y)]+=1\n",
    "            bian[(a,b)]+=1\n",
    "            bian[(x,b)]+=1\n",
    "            bian[(a,y)]+=1\n",
    "        state=True\n",
    "        if (x2-x1)*(y2-y1)!=total:\n",
    "            return False\n",
    "        bian[(x1,y1)]+=1\n",
    "        bian[(x1,y2)]+=1\n",
    "        bian[(x2,y1)]+=1\n",
    "        bian[(x2,y2)]+=1\n",
    "        print(bian)\n",
    "        for val in bian.values():\n",
    "            if val%2!=0:\n",
    "                return False\n",
    "        return state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        Y = []\n",
    "        addr = []\n",
    "        for i,a,j,b in rectangles:\n",
    "            a *= 2;b *= 2\n",
    "            Y.extend([a,b,a+1,b+1])\n",
    "            addr.append([i,a,b,1])\n",
    "            addr.append([j,a,b,0])\n",
    "        Y = sorted(set(Y))\n",
    "        diffArr = [0]*len(Y)\n",
    "        rank = defaultdict(int)\n",
    "        height = [0] * len(Y)\n",
    "        for i,j in enumerate(Y):\n",
    "            rank[j] = i\n",
    "            if i:height[i] = j-Y[i-1]\n",
    "        addr.sort()\n",
    "        area = 0\n",
    "        pre = addr[0][0]\n",
    "        ans = 0\n",
    "        for a,b,c,d in rectangles:\n",
    "            ans += (c-a)*(d-b)*2\n",
    "        for x,y1,y2,flag in addr:\n",
    "            if pre != x:\n",
    "                width,isCover,last,tmp =x-pre, 0,-2,0\n",
    "                for i,j in enumerate(diffArr):\n",
    "                    isCover += j\n",
    "                    if isCover > 0:\n",
    "                        if last + 1 == i:\n",
    "                            tmp += height[i]\n",
    "                        last = i\n",
    "                if area and tmp != area:\n",
    "                    return False\n",
    "                area = tmp\n",
    "                ans -= tmp*width\n",
    "                pre = x\n",
    "            if flag:diffArr[rank[y1]] += 1;diffArr[rank[y2+1]] -= 1\n",
    "            else:diffArr[rank[y1]] -= 1;diffArr[rank[y2+1]] += 1\n",
    "        return ans == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        Y = []\n",
    "        addr = []\n",
    "        for i,a,j,b in rectangles:\n",
    "            a *= 2;b *= 2\n",
    "            Y.extend([a,b,a+1,b+1])\n",
    "            addr.append([i,a,b,1])\n",
    "            addr.append([j,a,b,-1])\n",
    "        Y = sorted(set(Y))\n",
    "        diffArr = [0]*len(Y)\n",
    "        rank = defaultdict(int)\n",
    "        height = [0] * len(Y)\n",
    "        for i,j in enumerate(Y):\n",
    "            rank[j] = i\n",
    "            if i:height[i] = j-Y[i-1]\n",
    "        addr.sort()\n",
    "        area = 0\n",
    "        pre = addr[0][0]\n",
    "        ans = 0\n",
    "        for a,b,c,d in rectangles:\n",
    "            ans += (c-a)*(d-b)*2\n",
    "        for x,y1,y2,flag in addr:\n",
    "            if pre != x:\n",
    "                width,isCover,last,tmp =x-pre, 0,-2,0\n",
    "                for i,j in enumerate(diffArr):\n",
    "                    isCover += j\n",
    "                    if isCover > 0:\n",
    "                        if last + 1 == i:\n",
    "                            tmp += height[i]\n",
    "                        last = i\n",
    "                if area and tmp != area:\n",
    "                    return False\n",
    "                area = tmp\n",
    "                ans -= tmp*width\n",
    "                pre = x\n",
    "            if flag >0:diffArr[rank[y1]] += 1;diffArr[rank[y2+1]] -= 1\n",
    "            else:diffArr[rank[y1]] -= 1;diffArr[rank[y2+1]] += 1\n",
    "        return ans == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        vertex_set = set()\n",
    "        area_sum = 0\n",
    "        for rect in rectangles:\n",
    "            x1, y1, x2, y2 = rect\n",
    "            area_sum += (x2 - x1) * (y2 - y1)\n",
    "            for vertex in [(x1, y1), (x1, y2), (x2, y1), (x2, y2)]:\n",
    "                if vertex in vertex_set:\n",
    "                    vertex_set.remove(vertex)\n",
    "                else:\n",
    "                    vertex_set.add(vertex)\n",
    "        if len(vertex_set) != 4:\n",
    "            return False\n",
    "        min_x, min_y = min(vertex_set)\n",
    "        max_x, max_y = max(vertex_set)\n",
    "        expected_area = (max_x - min_x) * (max_y - min_y)\n",
    "        if area_sum != expected_area:\n",
    "            return False\n",
    "        count = {}\n",
    "        for rect in rectangles:\n",
    "            x1, y1, x2, y2 = rect\n",
    "            for vertex in [(x1, y1), (x1, y2), (x2, y1), (x2, y2)]:\n",
    "                if vertex in count:\n",
    "                    count[vertex] += 1\n",
    "                else:\n",
    "                    count[vertex] = 1\n",
    "        for vertex, c in count.items():\n",
    "            if vertex in [(min_x, min_y), (min_x, max_y), (max_x, min_y), (max_x, max_y)]:\n",
    "                if c != 1:\n",
    "                    return False\n",
    "            else:\n",
    "                if c % 2 == 1:\n",
    "                    return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        Y = []\n",
    "        addr = []\n",
    "        for i,a,j,b in rectangles:\n",
    "            a *= 2;b *= 2\n",
    "            Y.extend([a,b,a+1,b+1])\n",
    "            addr.append([i,a,b,1])\n",
    "            addr.append([j,a,b,-1])\n",
    "        Y = sorted(set(Y))\n",
    "        diffArr = [0]*len(Y)\n",
    "        rank = defaultdict(int)\n",
    "        height = [0] * len(Y)\n",
    "        for i,j in enumerate(Y):\n",
    "            rank[j] = i\n",
    "            if i:height[i] = j-Y[i-1]\n",
    "        addr.sort()\n",
    "        area = 0\n",
    "        pre = addr[0][0]\n",
    "        res = 0\n",
    "        for x,y1,y2,flag in addr:\n",
    "            if pre != x:\n",
    "                width,isCover,last,tmp =x-pre, 0,-2,0\n",
    "                for i,j in enumerate(diffArr):\n",
    "                    isCover += j\n",
    "                    if isCover > 0:\n",
    "                        if last + 1 == i:tmp += height[i]\n",
    "                        last = i\n",
    "                if area and tmp != area:\n",
    "                    return False\n",
    "                area = tmp\n",
    "                res += tmp*width\n",
    "                pre = x\n",
    "            if flag >0:diffArr[rank[y1]] += 1;diffArr[rank[y2+1]] -= 1\n",
    "            else:diffArr[rank[y1]] -= 1;diffArr[rank[y2+1]] += 1\n",
    "        ans = 0\n",
    "        for a,b,c,d in rectangles:\n",
    "            ans += (c-a)*(d-b)\n",
    "        print(ans,res)\n",
    "        print(11)\n",
    "        return res == ans*2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles):\n",
    "        def get_basic_info(rectangle):\n",
    "            x1, y1, x2, y2 = rectangle\n",
    "            area = (x2 - x1) * (y2 - y1)\n",
    "            return [(x1, y1), (x2, y1), (x1, y2), (x2, y2)], area\n",
    "\n",
    "        def get_all_vertexes_and_area(rectangles):\n",
    "            \n",
    "            all_vertexes, total_area = [], 0\n",
    "            for rect in rectangles:\n",
    "                vertexes, area = get_basic_info(rect)\n",
    "                all_vertexes += vertexes\n",
    "                total_area += area\n",
    "            return all_vertexes, total_area\n",
    "\n",
    "        def analize_vertexes(vertexes):\n",
    "            \"\"\"\n",
    "            分析顶点，类似游戏连连看，有重复顶点去掉这一对\n",
    "            :param vertexes:\n",
    "            :return:\n",
    "            \"\"\"\n",
    "            amount_dict = Counter(vertexes)\n",
    "            even_vetexes, odd_vetexes = {}, {}\n",
    "            for key, value in amount_dict.items():\n",
    "                if value %2 == 0:\n",
    "                    even_vetexes[key] = value\n",
    "                else:\n",
    "                    odd_vetexes[key] = value\n",
    "            return even_vetexes, odd_vetexes\n",
    "\n",
    "        def get_rectangle_area(vertexes):\n",
    "            x_list = [vertex[0] for vertex in vertexes]\n",
    "            y_list = [vertex[1] for vertex in vertexes]\n",
    "            l, r, b, t = min(x_list), max(x_list), min(y_list), max(y_list)\n",
    "            if sorted([(l, b), (r, b), (l, t), (r, t)]) == sorted(vertexes):\n",
    "                return (r-l) * (t-b)\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        def analize_odd_vertexes(vertex_records, area):\n",
    "            if len(vertex_records) == 4 and sum(vertex_records.values()) == 4:\n",
    "                vertexes = vertex_records.keys()\n",
    "                target_area = get_rectangle_area(vertexes)\n",
    "                if target_area == area:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        def is_perfect(rectangles):\n",
    "            vertexes, area = get_all_vertexes_and_area(rectangles)\n",
    "            even, odd = analize_vertexes(vertexes)\n",
    "            if analize_odd_vertexes(odd, area):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return is_perfect(rectangles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        def help(rec):\n",
    "            return (rec[0], rec[1]), (rec[2], rec[3]), (rec[0], rec[3]), (rec[2], rec[1])\n",
    "\n",
    "        if len(rectangles) == 1:\n",
    "            return True  \n",
    "\n",
    "        vertex = []\n",
    "        area = 0\n",
    "        for rec in rectangles:\n",
    "            vertex += help(rec)\n",
    "            area += (rec[2] - rec[0]) * (rec[3] - rec[1])\n",
    "\n",
    "        a = Counter(vertex)\n",
    "        b = sorted(a.items(), key=lambda x: x[1])\n",
    "        #验证边界点需满足条件  四个点只属于一个矩形  其他点属于2或者4个矩形\n",
    "        for i in range(len(b)):\n",
    "            if i<4 and b[i][1] > 1:\n",
    "                return False\n",
    "            elif i>3 and b[i][1]!=2 and b[i][1]!=4: #包含这个不是边界点的矩形数量必须为2或者4\n",
    "                return False\n",
    "        \n",
    "        # 验证这四个边界点是否能组成矩形\n",
    "        c = sorted(b[:4])\n",
    "        if c[0][0][0] != c[1][0][0] or c[0][0][1] != c[2][0][1] or c[3][0][0] != c[2][0][0] or c[3][0][1] != c[1][0][1]:\n",
    "            return False\n",
    "        \n",
    "        # 验证四个点组成矩形面积 是否等于所有矩形面积之和\n",
    "        return area == (c[3][0][0] - c[0][0][0]) * (c[3][0][1] - c[0][0][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    def helper(self, parts, part):\n",
    "        l = 0\n",
    "        r = len(parts) - 1\n",
    "        target_index = -1\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if parts[mid][1] < part[0]:\n",
    "                target_index = max(target_index, mid)\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        if target_index < len(parts) - 1:\n",
    "            if parts[target_index + 1][0] <= part[1]:\n",
    "                return False\n",
    "            elif parts[target_index + 1][0] == part[1] + 1:\n",
    "                part[1] = parts[target_index + 1][1]\n",
    "                parts.pop(target_index + 1)\n",
    "        if target_index >= 0 and part[0] == parts[target_index][1]+1:\n",
    "            parts[target_index][1] = part[1]\n",
    "        else:\n",
    "            parts.insert(target_index+1, part)\n",
    "        return True\n",
    "\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        v0 = rectangles[0][0]\n",
    "        v1 = rectangles[0][1]\n",
    "        v2 = rectangles[0][2]\n",
    "        v3 = rectangles[0][3]\n",
    "        for rectangle in rectangles:\n",
    "            v0 = min(v0, rectangle[0])\n",
    "            v1 = min(v1, rectangle[1])\n",
    "            v2 = max(v2, rectangle[2])\n",
    "            v3 = max(v3, rectangle[3])\n",
    "        rows = []\n",
    "        for i in range(v2-v0):\n",
    "            rows.append([])\n",
    "        total = (v2-v0) * (v3-v1)\n",
    "        for rectangle in rectangles:\n",
    "            for i in range(rectangle[0] - v0, rectangle[2]-v0):\n",
    "                new_part = [rectangle[1] - v1, rectangle[3] - v1 -1]\n",
    "                if not self.helper(rows[i], new_part):\n",
    "                    return False\n",
    "                total -= (rectangle[3] - rectangle[1])\n",
    "        return total == 0\n",
    "        \"\"\"\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "            m = {}\n",
    "            for rectangle in rectangles:\n",
    "                p1 = \"%s-%s\" % (rectangle[0], rectangle[1])\n",
    "                if p1 not in m:\n",
    "                    m[p1] = set()\n",
    "                if 1 in m[p1]:\n",
    "                    return False\n",
    "                else:\n",
    "                    m[p1].add(1)\n",
    "                p2 = \"%s-%s\" % (rectangle[0], rectangle[3])\n",
    "                if p2 not in m:\n",
    "                    m[p2] = set()\n",
    "                if 2 in m[p2]:\n",
    "                    return False\n",
    "                else:\n",
    "                    m[p2].add(2)\n",
    "                p3 = \"%s-%s\" % (rectangle[2], rectangle[3])\n",
    "                if p3 not in m:\n",
    "                    m[p3] = set()\n",
    "                if 3 in m[p3]:\n",
    "                    return False\n",
    "                else:\n",
    "                    m[p3].add(3)\n",
    "                p4 = \"%s-%s\" % (rectangle[2], rectangle[1])\n",
    "                if p4 not in m:\n",
    "                    m[p4] = set()\n",
    "                if 4 in m[p4]:\n",
    "                    return False\n",
    "                else:\n",
    "                    m[p4].add(4)\n",
    "            major = 0\n",
    "            for key in m:\n",
    "                val = list(m[key])\n",
    "                l = len(val)\n",
    "                if l == 1:\n",
    "                    major += 1\n",
    "                elif l == 2:\n",
    "                    if abs(val[0] - val[1]) == 2:\n",
    "                        return False\n",
    "                elif l == 4:\n",
    "                    pass\n",
    "                else:\n",
    "                    return False\n",
    "            return major == 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        exp_area = 0\n",
    "        point_dict = {}\n",
    "        rec_sets0 = [tuple(ll) for ll in rectangles]\n",
    "        rec_list = list(set(rec_sets0))\n",
    "        if len(rec_list) != len(rectangles):\n",
    "            return False\n",
    "\n",
    "        for rectangle in rec_list:\n",
    "            exp_area += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1])\n",
    "            p1 = (rectangle[0], rectangle[1])\n",
    "            p2 = (rectangle[0], rectangle[3])\n",
    "            p3 = (rectangle[2], rectangle[1])\n",
    "            p4 = (rectangle[2], rectangle[3])\n",
    "            point_dict[p1] = point_dict.get(p1, 0) + 1\n",
    "            point_dict[p2] = point_dict.get(p2, 0) + 1\n",
    "            point_dict[p3] = point_dict.get(p3, 0) + 1\n",
    "            point_dict[p4] = point_dict.get(p4, 0) + 1\n",
    "        single_points = []\n",
    "        for key, value in point_dict.items():\n",
    "            if value == 1:\n",
    "                single_points.append(key)\n",
    "        if len(single_points) != 4:\n",
    "            return False\n",
    "        single_points.sort(key=lambda x: x[0])\n",
    "        # single_points = sorted(single_points, key=lambda x: x[0])\n",
    "        rst_area = abs((single_points[1][1] - single_points[0][1]) * (single_points[2][0] - single_points[0][0]))\n",
    "        if rst_area != exp_area:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        exp_area = 0\n",
    "        point_dict = {}\n",
    "        rec_sets0 = [tuple(ll) for ll in rectangles]\n",
    "        rec_list = list(set(rec_sets0))\n",
    "        if len(rec_list) != len(rectangles):\n",
    "            return False\n",
    "\n",
    "        for rectangle in rec_list:\n",
    "            exp_area += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1])\n",
    "            p1 = (rectangle[0], rectangle[1])\n",
    "            p2 = (rectangle[0], rectangle[3])\n",
    "            p3 = (rectangle[2], rectangle[1])\n",
    "            p4 = (rectangle[2], rectangle[3])\n",
    "            point_dict[p1] = point_dict.get(p1, 0) + 1\n",
    "            point_dict[p2] = point_dict.get(p2, 0) + 1\n",
    "            point_dict[p3] = point_dict.get(p3, 0) + 1\n",
    "            point_dict[p4] = point_dict.get(p4, 0) + 1\n",
    "        single_points = []\n",
    "        for key, value in point_dict.items():\n",
    "            if value == 1:\n",
    "                single_points.append(key)\n",
    "        if len(single_points) != 4:\n",
    "            return False\n",
    "        single_points.sort(key=lambda x: x[0])\n",
    "        # single_points = sorted(single_points, key=lambda x: x[0])\n",
    "        rst_area = abs((single_points[1][1] - single_points[0][1]) * (single_points[2][0] - single_points[0][0]))\n",
    "        if rst_area != exp_area:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        area_sum = 0\n",
    "        dots = []\n",
    "        for rec in rectangles:\n",
    "            area_sum += (rec[2] - rec[0]) * (rec[3] - rec[1])\n",
    "            dots.append(rec[0:2])\n",
    "            dots.append(rec[2:4])\n",
    "            dots.append([rec[0], rec[3]])\n",
    "            dots.append([rec[2], rec[1]])\n",
    "        vertices = {}\n",
    "        for dot in dots:\n",
    "            key = tuple(dot)\n",
    "            if key not in vertices:\n",
    "                vertices[key] = 1\n",
    "            else:\n",
    "                vertices[key] += 1\n",
    "        ver = [v for v in vertices if vertices[v] % 2 == 1]\n",
    "        if len(ver) != 4:\n",
    "            return False\n",
    "        x = list({x for x, y in ver})\n",
    "        y = list({y for x, y in ver})\n",
    "        if not(len(x) == len(y) == 2):\n",
    "            return False\n",
    "        area = (x[0] - x[1]) * (y[0] - y[1])\n",
    "        if area == area_sum or area + area_sum == 0:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        area_sum = 0\n",
    "        # dots = [[i, i] for i in range(4 * len(rectangles))]\n",
    "        dots = []\n",
    "        for rec in rectangles:\n",
    "            area_sum += (rec[2] - rec[0]) * (rec[3] - rec[1])\n",
    "            dots.append(rec[0:2])\n",
    "            dots.append(rec[2:4])\n",
    "            dots.append([rec[0], rec[3]])\n",
    "            dots.append([rec[2], rec[1]])\n",
    "        vertices = {}\n",
    "        for dot in dots:\n",
    "            key = tuple(dot)\n",
    "            if key not in vertices:\n",
    "                vertices[key] = 1\n",
    "            else:\n",
    "                vertices[key] += 1\n",
    "        ver = [v for v in vertices if vertices[v] % 2 == 1]\n",
    "        del vertices\n",
    "        if len(ver) != 4:\n",
    "            return False\n",
    "        x = list({x for x, y in ver})\n",
    "        y = list({y for x, y in ver})\n",
    "        del ver\n",
    "        if not(len(x) == len(y) == 2):\n",
    "            return False\n",
    "        area = (x[0] - x[1]) * (y[0] - y[1])\n",
    "        if area == area_sum or area + area_sum == 0:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        x_min,y_min,x_max,y_max=rectangles[0]\n",
    "        def area_rec(rect):\n",
    "            return (rect[2]-rect[0])*(rect[3]-rect[1])\n",
    "        def cnt01(stack):\n",
    "            Y=[]\n",
    "            for i in stack:\n",
    "                Y.extend(dic[i])\n",
    "            Y.sort()\n",
    "            cnt=0\n",
    "            for y,i in Y:\n",
    "                if i:\n",
    "                    cnt+=1\n",
    "                    if cnt>1:\n",
    "                        return False\n",
    "                else:\n",
    "                    cnt-=1\n",
    "            return True\n",
    "                \n",
    "        all_areas=0\n",
    "        dic={}\n",
    "        X=[]\n",
    "        for i,rect in enumerate(rectangles):\n",
    "            all_areas+=area_rec(rect)\n",
    "            x_min=min(x_min,rect[0])\n",
    "            x_max=max(x_max,rect[2])\n",
    "            y_min=min(y_min,rect[1])\n",
    "            y_max=max(y_max,rect[3])\n",
    "            X.append([rect[0],1,i])\n",
    "            X.append([rect[2],0,i])\n",
    "            dic[i]=[[rect[1],1],[rect[3],0]]\n",
    "        if all_areas!=(x_max-x_min)*(y_max-y_min): return False\n",
    "        X.sort()\n",
    "        cnt=0\n",
    "        stack=[]\n",
    "        n=len(X)\n",
    "        ind=0\n",
    "        while ind<n:\n",
    "            while ind<n and X[ind][1]:\n",
    "                cnt+=1\n",
    "                \n",
    "                stack.append(X[ind][2])\n",
    "                ind+=1\n",
    "            if cnt>1:\n",
    "                if not cnt01(stack): return False\n",
    "            while ind<n and (not X[ind][1]):\n",
    "                cnt-=1\n",
    "                \n",
    "                stack.remove(X[ind][2])\n",
    "                ind+=1\n",
    "        \n",
    "        \n",
    "#         for x,l,i in X:\n",
    "#             if not l:\n",
    "#                 cnt-=1\n",
    "#                 stack.remove(i)\n",
    "#             else:\n",
    "#                 cnt+=1\n",
    "#                 stack.append(i)\n",
    "#                 if cnt>1:\n",
    "#                     if not cnt01(stack): return False\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: [[int]]) -> bool:\n",
    "        mx1, my1, mx2, my2 = rectangles[0]\n",
    "        mx11, my11, mx22, my22 = rectangles[0]\n",
    "        areas = []\n",
    "        x1s, x2s, y1s, y2s = set(), set(), set(), set()\n",
    "\n",
    "        rectangles_set = set()\n",
    "\n",
    "        point_cnt = {}\n",
    "        for xyi in rectangles:\n",
    "\n",
    "            xyi_t = tuple(xyi)\n",
    "            if xyi_t in rectangles_set:\n",
    "                return False\n",
    "            rectangles_set.add(xyi_t)\n",
    "            x1, y1, x2, y2 = xyi\n",
    "            areas.append((y2 - y1) * (x2 - x1))\n",
    "\n",
    "            if x1 <= mx1 and y1 <= my1:\n",
    "                mx1, my1 = x1, y1\n",
    "\n",
    "            if x2 >= mx2 and y2 >= my2:\n",
    "                mx2, my2 = x2, y2\n",
    "\n",
    "            point_cnt[(x1, y1)] = point_cnt.get((x1, y1), 0) + 1\n",
    "            point_cnt[(x1, y2)] = point_cnt.get((x1, y2), 0) + 1\n",
    "            point_cnt[(x2, y1)] = point_cnt.get((x2, y1), 0) + 1\n",
    "            point_cnt[(x2, y2)] = point_cnt.get((x2, y2), 0) + 1\n",
    "\n",
    "            x1s.add(x1)\n",
    "            x2s.add(x2)\n",
    "            y1s.add(y1)\n",
    "            y2s.add(y2)\n",
    "\n",
    "        j_point = []\n",
    "\n",
    "        # mx11, my11, mx22, my22 =\n",
    "\n",
    "        mpoint = [(mx1, my1), (mx1, my2), (mx2, my1), (mx2, my2)]\n",
    "        for k in point_cnt:\n",
    "            if point_cnt[k] % 2 == 1:\n",
    "                if k not in mpoint:\n",
    "                    return False\n",
    "                j_point.append(list(k) + [point_cnt[k]])\n",
    "                mx11 = min(mx11, k[0])\n",
    "                mx22 = max(mx22, k[0])\n",
    "                my11 = min(my11, k[1])\n",
    "                my22 = max(my22, k[1])\n",
    "                # print(k, point_cnt[k])\n",
    "\n",
    "        # print(j_point)\n",
    "        if len(j_point) != 4:\n",
    "            return False\n",
    "\n",
    "        mxy = [mx1, my1, mx2, my2]\n",
    "        mxyy = [mx11, my11, mx22, my22]\n",
    "        # print('\\n' * 3)\n",
    "        # print(rectangles)\n",
    "        t = list(x1s - x2s), list(y1s - y2s), list(x2s - x1s), list(y2s - y1s)\n",
    "        # print('#1#', 't', t, 'mxy', mxy)\n",
    "        if (my2 - my1) * (mx2 - mx1) != sum(areas):\n",
    "            return False\n",
    "        # print('#2#', 't', t, 'mxy', mxy)\n",
    "        for tt in t:\n",
    "            if len(tt) != 1:\n",
    "                return False\n",
    "\n",
    "        t = [tt[0] for tt in t]\n",
    "\n",
    "        # print('#3#', 't', t, 'mxy', mxy)\n",
    "        for tt, mxyi, mxyyi in zip(t, mxy, mxyy):\n",
    "            if tt != mxyi:\n",
    "                return False\n",
    "            if tt != mxyyi:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        points={}\n",
    "        for r in rectangles:\n",
    "            corners=r[0]*1000000+r[1],r[2]*1000000+r[1],r[0]*1000000+r[3],r[2]*1000000+r[3]\n",
    "            for i in range(4):\n",
    "                if corners[i] not in points.keys():\n",
    "                    points[corners[i]]=[0,0,0,0]\n",
    "                if points[corners[i]][i]==1:\n",
    "                    return False\n",
    "                points[corners[i]][i]=1\n",
    "        c=0\n",
    "        for p in points:\n",
    "            v=points[p]\n",
    "            if sum(v)==1:\n",
    "                c+=1\n",
    "                if c>4:\n",
    "                    return False\n",
    "            if sum(v)==3:\n",
    "                return False\n",
    "            if sum(v)==2:\n",
    "                if v[0]==v[3]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        points = []; areaSum = 0\n",
    "        for r in rectangles:\n",
    "            points.append((r[0],r[1]))\n",
    "            points.append((r[2],r[3]))\n",
    "            points.append((r[0],r[3]))\n",
    "            points.append((r[2],r[1]))\n",
    "            areaSum += (r[3]-r[1])*(r[2]-r[0])\n",
    "        c = Counter(points)\n",
    "        dingdian = []\n",
    "        for k,v in c.items():\n",
    "            if v == 1: dingdian.append(k)\n",
    "            elif v % 2: return False\n",
    "        if len(dingdian) != 4: return False\n",
    "        a,b = list(zip(*dingdian))\n",
    "        bigArea = (max(a)-min(a))*(max(b)-min(b))\n",
    "        if areaSum != bigArea: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        min_x,max_x,min_y,max_y,area=1000000000,-1000000000,100000000,-100000000,0\n",
    "        for r in rectangles:\n",
    "            if r[0]<min_x:\n",
    "                min_x=r[0]\n",
    "            if r[1]<min_y:\n",
    "                min_y=r[1]\n",
    "            if r[2]>max_x:\n",
    "                max_x=r[2]\n",
    "            if r[3]>max_y:\n",
    "                max_y=r[3]\n",
    "            area+=(r[3]-r[1])*(r[2]-r[0])\n",
    "        if (max_x-min_x)*(max_y-min_y)!=area:\n",
    "            return False\n",
    "        points={}\n",
    "        for r in rectangles:\n",
    "            corners=(r[0],r[1]),(r[2],r[1]),(r[0],r[3]),(r[2],r[3])\n",
    "            for i in range(4):\n",
    "                if corners[i] not in points.keys():\n",
    "                    points[corners[i]]=[0,0,0,0]\n",
    "                if points[corners[i]][i]==1:\n",
    "                    return False\n",
    "                points[corners[i]][i]=1\n",
    "        c=0\n",
    "        for p in points:\n",
    "            v=points[p]\n",
    "            if sum(v)==1:\n",
    "                c+=1\n",
    "                if c>4:\n",
    "                    return False\n",
    "            if sum(v)==3:\n",
    "                return False\n",
    "            if sum(v)==2:\n",
    "                if v[0]==v[3]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        points={}\n",
    "        for r in rectangles:\n",
    "            corners=(r[0],r[1]),(r[2],r[1]),(r[0],r[3]),(r[2],r[3])\n",
    "            for i in range(4):\n",
    "                if corners[i] not in points.keys():\n",
    "                    points[corners[i]]=[0,0,0,0]\n",
    "                if points[corners[i]][i]==1:\n",
    "                    return False\n",
    "                points[corners[i]][i]=1\n",
    "        c=0\n",
    "        for p in points:\n",
    "            v=points[p]\n",
    "            if sum(v)==1:\n",
    "                c+=1\n",
    "                if c>4:\n",
    "                    return False\n",
    "            if sum(v)==3:\n",
    "                return False\n",
    "            if sum(v)==2:\n",
    "                if v[0]==v[3]:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        t = []\n",
    "        for i in rectangles:\n",
    "            t.extend([i[:2],i[2:],[i[0],i[3]],[i[2],i[1]]])\n",
    "        t.sort(key=lambda x:[x[0],x[1]])\n",
    "        s = sum([(x[2]-x[0])*(x[3]-x[1]) for x in rectangles])\n",
    "        r = []\n",
    "        for i in t:\n",
    "            if i not in r:\n",
    "                r.append(i)\n",
    "            else:\n",
    "                r.remove(i)\n",
    "        r.sort(key=lambda x:[x[0],x[1]])\n",
    "        print(s,r)\n",
    "        if len(r) == 4 and s == (r[3][0]-r[0][0])*(r[3][1]-r[0][1]):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        s = 0\n",
    "        a, b, c, dd = math.inf, math.inf, 0, 0\n",
    "        d = [defaultdict(int) for _ in range(4)]\n",
    "        t = defaultdict(int)\n",
    "        for i, j, m, n in rectangles:\n",
    "            s += (m - i) * (n - j)\n",
    "            a = min(i, a)\n",
    "            b = min(j, b)\n",
    "            c = max(m, c)\n",
    "            dd = max(n, dd)\n",
    "            d[0][i, j] += 1\n",
    "            t[i, j] += 1\n",
    "            d[1][m, n] += 1\n",
    "            t[m, n] += 1\n",
    "            d[2][i, n] += 1\n",
    "            t[i, n] += 1\n",
    "            d[3][m, j] += 1\n",
    "            t[m, j] += 1\n",
    "        if s != (dd - b) * (c - a): \n",
    "            return False\n",
    "        for j in range(4):\n",
    "            s = 0\n",
    "            for k, i in d[j].items():\n",
    "                if i > 1: \n",
    "                    return False\n",
    "                elif t[k] == 1:\n",
    "                    s += 1\n",
    "            if s != 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        a={}\n",
    "        b1={}\n",
    "        b2={}\n",
    "        b3={}\n",
    "        b4={}\n",
    "        for i in rectangles:\n",
    "            \n",
    "            q1=str(i[0])+'.'+str(i[1])\n",
    "            q2=str(i[0])+'.'+str(i[3])\n",
    "            q3=str(i[2])+'.'+str(i[1])\n",
    "            q4=str(i[2])+'.'+str(i[3])\n",
    "            if q1 in b1:\n",
    "                return False\n",
    "            b1[q1]=0\n",
    "            if q2 in b2:\n",
    "                return False\n",
    "            b2[q2]=0\n",
    "            if q3 in b3:\n",
    "                return False\n",
    "            b3[q3]=0\n",
    "            if q4 in b4:\n",
    "                return False\n",
    "            b4[q4]=0\n",
    "            if q1 in a:\n",
    "                a[q1]+=1\n",
    "            else:\n",
    "                a[q1]=1\n",
    "            if q2 in a:\n",
    "                a[q2]+=1\n",
    "            else:\n",
    "                a[q2]=1\n",
    "            if q3 in a:\n",
    "                a[q3]+=1\n",
    "            else:\n",
    "                a[q3]=1\n",
    "            if q4 in a:\n",
    "                a[q4]+=1\n",
    "            else:\n",
    "                a[q4]=1\n",
    "        r=0\n",
    "        for i in a:\n",
    "            if a[i]==3:\n",
    "                return False\n",
    "            if a[i]>4:\n",
    "                return False\n",
    "            if a[i]==1:\n",
    "                r+=1\n",
    "                if r>4:\n",
    "                    return False\n",
    "        if r!=4:\n",
    "            return False\n",
    "        \n",
    "        for i in b1:\n",
    "            if i in b4:\n",
    "                if i not in b2 or i not in b3:\n",
    "                    return False\n",
    "        for i in b4:\n",
    "            if i in b1:\n",
    "                if i not in b2 or i not in b3:\n",
    "                    return False\n",
    "        for i in b2:\n",
    "            if i in b3:\n",
    "                if i not in b1 or i not in b4:\n",
    "                    return False\n",
    "        for i in b3:\n",
    "            if i in b2:\n",
    "                if i not in b1 or i not in b4:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        \n",
    "\n",
    "        def get_bin_l(arr_s, ss, ee):\n",
    "            # print(\"arr is\", arr_s, \"ss, ee =\", ss, ee)\n",
    "            last_end = ss\n",
    "            for ys, ye in arr_s:\n",
    "                if last_end != ys:\n",
    "                    return False\n",
    "                last_end = ye\n",
    "            if last_end != ee:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        miny, maxy = 9999999, -9999999\n",
    "        lst = []\n",
    "        xxmax = -999999999\n",
    "        for x1,y1,x2,y2 in rectangles:\n",
    "            if x1 == x2:\n",
    "                continue\n",
    "            lst.append([x1, y1, y2, 1])\n",
    "            lst.append([x1+0.5, y1, y2, 0])\n",
    "            lst.append([x2, y1, y2, -1])\n",
    "            lst.append([x2+0.5, y1, y2, 0])\n",
    "            miny = min(miny, y1)\n",
    "            maxy = max(maxy, y2)\n",
    "\n",
    "        lst.sort(key = lambda x:x[0]*10000+x[3]*0.00001)\n",
    "        xxmax = lst[-1][0]\n",
    "        # print(\"lst =\", lst)\n",
    "        now = []\n",
    "        res = 0\n",
    "        for x, y1, y2, f in lst:\n",
    "            if f == 0:\n",
    "                res = get_bin_l(now, miny, maxy)\n",
    "                if res == False and x < xxmax - 0.1:\n",
    "                    return False\n",
    "                continue\n",
    "            if f == 1:\n",
    "                now.append([y1, y2])\n",
    "            else:\n",
    "                now.remove([y1, y2])\n",
    "            now.sort()\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        x_count = {}\n",
    "        y_count = {}\n",
    "        map_l={}\n",
    "        map_r={}\n",
    "        count = 0\n",
    "        for rec in rectangles:\n",
    "            if (rec[0],rec[1]) in map_l or (rec[2],rec[3]) in map_r:\n",
    "                return False\n",
    "            else:\n",
    "                map_l[(rec[0],rec[1])]=0\n",
    "                map_r[(rec[2],rec[3])]=0\n",
    "            for x in range(rec[0],rec[2]):\n",
    "                if x in x_count:\n",
    "                    x_count[x]+= rec[3]-rec[1]\n",
    "                else:\n",
    "                    x_count[x] = rec[3]-rec[1]\n",
    "            for y in range(rec[1],rec[3]):\n",
    "                if y in y_count:\n",
    "                    y_count[y] += rec[2] - rec[0]\n",
    "                else:\n",
    "                    y_count[y] = rec[2] - rec[0]\n",
    "            count += (rec[3]-rec[1])*(rec[2]-rec[0])\n",
    "            \n",
    "        x = list(x_count.values())\n",
    "        y = list(y_count.values())\n",
    "\n",
    "        if max(x)!=min(x) or max(y)!=min(y):\n",
    "            return False\n",
    "\n",
    "        x_d = sorted(list(x_count.keys()))\n",
    "        y_d = sorted(list(y_count.keys()))\n",
    "\n",
    "        if count != (x_d[-1]-x_d[0]+1)*(y_d[-1]-y_d[0]+1):\n",
    "            return False\n",
    "\n",
    "        return True\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        n = len(rectangles)\n",
    "        tx = min([rectangles[i][0] for i in range(n)])\n",
    "        ty = min([rectangles[i][1] for i in range(n)])\n",
    "        ta = max([rectangles[i][2] for i in range(n)])\n",
    "        tb = max([rectangles[i][3] for i in range(n)])\n",
    "\n",
    "        def isConLine(intervals):\n",
    "            for i in range(1, len(intervals)):\n",
    "                if intervals[i][0] == intervals[i-1][1]:\n",
    "                    continue\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        # merge left side\n",
    "        left = [[rectangles[i][1], rectangles[i][3]] for i in range(n) if rectangles[i][0] == tx]\n",
    "        if not isConLine(sorted(left)): return False\n",
    "        # merge right side\n",
    "        right = [[rectangles[i][1], rectangles[i][3]] for i in range(n) if rectangles[i][2] == ta]\n",
    "        if not isConLine(sorted(right)): return False\n",
    "        # merge up side\n",
    "        up = [[rectangles[i][0], rectangles[i][2]] for i in range(n) if rectangles[i][3] == tb]\n",
    "        if not isConLine(sorted(up)): return False\n",
    "        # merge down side\n",
    "        down = [[rectangles[i][0], rectangles[i][2]] for i in range(n) if rectangles[i][1] == ty]\n",
    "        if not isConLine(sorted(down)): return False\n",
    "\n",
    "        def mergeLinesNoCross(lines):\n",
    "            lines.sort()\n",
    "            merged = []\n",
    "            for s, e in lines:\n",
    "                if not merged:\n",
    "                    merged.append([s, e])\n",
    "                    continue\n",
    "                if s < merged[-1][1]:\n",
    "                    return []\n",
    "                if s == merged[-1][1]:\n",
    "                    merged[-1][1] = e\n",
    "                else:\n",
    "                    merged.append([s, e])\n",
    "            return merged\n",
    "\n",
    "        # check internal vertical line\n",
    "        def dictList():\n",
    "            dictlist = {1:[], -1:[]}\n",
    "            return dictlist\n",
    "        ver_lines = defaultdict(dictList)\n",
    "        for x, y, a, b in rectangles:\n",
    "            # igore outer lines\n",
    "            if x != tx:\n",
    "                ver_lines[x][1].append([y, b])\n",
    "            if a != ta:\n",
    "                ver_lines[a][-1].append([y, b])\n",
    "        print(ver_lines.items())\n",
    "\n",
    "        for x, lrlines in ver_lines.items():\n",
    "            merged_left = mergeLinesNoCross(lrlines[1])\n",
    "            print(merged_left)\n",
    "            if not merged_left: return False\n",
    "            merged_right = mergeLinesNoCross(lrlines[-1])\n",
    "            print(merged_right)\n",
    "            if not merged_right: return False\n",
    "            if merged_left != merged_right:\n",
    "                return False\n",
    "        return True\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        p, q, r, s = float('inf'), float('inf'), float('-inf'), float('-inf')\n",
    "        t = 0\n",
    "        for a, b, c, d in rectangles:\n",
    "            p = min(p, a)\n",
    "            q = min(q, b)\n",
    "            r = max(r, c)\n",
    "            s = max(s, d)\n",
    "            t += (c - a) * (d - b)\n",
    "        if t != (r - p) * (s - q):\n",
    "            return False\n",
    "        points = {}\n",
    "        mins = float('inf')\n",
    "        for x, y, u, v in rectangles:\n",
    "            if (x, y) in points:\n",
    "                return False\n",
    "            else:\n",
    "                points[(x, y)] = [(u, v), (u, y), (x, v)]\n",
    "                if x == p:\n",
    "                    mins = min(mins, y)\n",
    "        queue = deque([(p, mins)])\n",
    "        visited = set([(p, mins)])\n",
    "        while queue:\n",
    "            x, y = queue.popleft()\n",
    "            if (x, y) in points:\n",
    "                for a, b in points[(x, y)]:\n",
    "                    if (a, b) not in visited:\n",
    "                        visited.add((a, b))\n",
    "                        queue.append((a, b))\n",
    "        for x, y in points:\n",
    "            if (x, y) not in visited:\n",
    "                return False\n",
    "        if (p, q) in visited and (p, s) in visited and (r, q) in visited and (r, s) in visited:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 线段树的节点类\n",
    "class SegTreeNode:\n",
    "    def __init__(self, val=0):\n",
    "        self.left = -1                              # 区间左边界\n",
    "        self.right = -1                             # 区间右边界\n",
    "        self.val = val                              # 节点值（区间值）\n",
    "        self.lazy_tag = None                        # 区间和问题的延迟更新标记\n",
    "        \n",
    "        \n",
    "        # 线段树类\n",
    "class SegmentTree:\n",
    "    # 初始化线段树接口\n",
    "    def __init__(self, nums, function):\n",
    "        self.size = len(nums)\n",
    "        self.tree = [SegTreeNode() for _ in range(4 * self.size)]  # 维护 SegTreeNode 数组\n",
    "        self.nums = nums                            # 原始数据\n",
    "        self.function = function                    # function 是一个函数，左右区间的聚合方法\n",
    "        if self.size > 0:\n",
    "            self.__build(0, 0, self.size - 1)\n",
    "            \n",
    "            # 单点更新接口：将 nums[i] 更改为 val\n",
    "    def update_point(self, i, val):\n",
    "        self.nums[i] = val\n",
    "        self.__update_point(i, val, 0)\n",
    "        \n",
    "        # 区间更新接口：将区间为 [q_left, q_right] 上的所有元素值加上 val\n",
    "    def update_interval(self, q_left, q_right, val):\n",
    "        self.__update_interval(q_left, q_right, val, 0)\n",
    "        \n",
    "        # 区间查询接口：查询区间为 [q_left, q_right] 的区间值\n",
    "    def query_interval(self, q_left, q_right):\n",
    "        return self.__query_interval(q_left, q_right, 0)\n",
    "    \n",
    "    # 获取 nums 数组接口：返回 nums 数组\n",
    "    def get_nums(self):\n",
    "        for i in range(self.size):\n",
    "            self.nums[i] = self.query_interval(i, i)\n",
    "        return self.nums\n",
    "    \n",
    "    \n",
    "    # 以下为内部实现方法\n",
    "    \n",
    "    # 构建线段树实现方法：节点的存储下标为 index，节点的区间为 [left, right]\n",
    "    def __build(self, index, left, right):\n",
    "        self.tree[index].left = left\n",
    "        self.tree[index].right = right\n",
    "        if left == right:                           # 叶子节点，节点值为对应位置的元素值\n",
    "            self.tree[index].val = self.nums[left]\n",
    "            return\n",
    "    \n",
    "        mid = left + (right - left) // 2            # 左右节点划分点\n",
    "        left_index = index * 2 + 1                  # 左子节点的存储下标\n",
    "        right_index = index * 2 + 2                 # 右子节点的存储下标\n",
    "        self.__build(left_index, left, mid)         # 递归创建左子树\n",
    "        self.__build(right_index, mid + 1, right)   # 递归创建右子树\n",
    "        self.__pushup(index)                        # 向上更新节点的区间值\n",
    "    \n",
    "        # 区间更新实现方法\n",
    "    def __update_interval(self, q_left, q_right, val, index):\n",
    "        left = self.tree[index].left\n",
    "        right = self.tree[index].right\n",
    "        \n",
    "        if left >= q_left and right <= q_right:     # 节点所在区间被 [q_left, q_right] 所覆盖        \n",
    "            if self.tree[index].lazy_tag is not None:\n",
    "                self.tree[index].lazy_tag += val    # 将当前节点的延迟标记增加 val\n",
    "            else:\n",
    "                self.tree[index].lazy_tag = val     # 将当前节点的延迟标记增加 val\n",
    "            self.tree[index].val += val \t\t# 当前节点所在区间每个元素值增加 val\n",
    "            return\n",
    "    \n",
    "        if right < q_left or left > q_right:        # 节点所在区间与 [q_left, q_right] 无关\n",
    "            return\n",
    "    \n",
    "        self.__pushdown(index)                      # 向下更新节点的区间值\n",
    "    \n",
    "        mid = left + (right - left) // 2            # 左右节点划分点\n",
    "        left_index = index * 2 + 1                  # 左子节点的存储下标\n",
    "        right_index = index * 2 + 2                 # 右子节点的存储下标\n",
    "        if q_left <= mid:                           # 在左子树中更新区间值\n",
    "            self.__update_interval(q_left, q_right, val, left_index)\n",
    "        if q_right > mid:                           # 在右子树中更新区间值\n",
    "            self.__update_interval(q_left, q_right, val, right_index)\n",
    "    \n",
    "        self.__pushup(index)                        # 向上更新节点的区间值\n",
    "    \n",
    "    # 区间查询实现方法：在线段树中搜索区间为 [q_left, q_right] 的区间值\n",
    "    def __query_interval(self, q_left, q_right, index):\n",
    "        left = self.tree[index].left\n",
    "        right = self.tree[index].right\n",
    "        \n",
    "        if left >= q_left and right <= q_right:     # 节点所在区间被 [q_left, q_right] 所覆盖\n",
    "            return self.tree[index].val             # 直接返回节点值\n",
    "        if right < q_left or left > q_right:        # 节点所在区间与 [q_left, q_right] 无关\n",
    "            return 0\n",
    "    \n",
    "        self.__pushdown(index)\n",
    "    \n",
    "        mid = left + (right - left) // 2            # 左右节点划分点\n",
    "        left_index = index * 2 + 1                  # 左子节点的存储下标\n",
    "        right_index = index * 2 + 2                 # 右子节点的存储下标\n",
    "        res_left = 0                                # 左子树查询结果\n",
    "        res_right = 0                               # 右子树查询结果\n",
    "        if q_left <= mid:                           # 在左子树中查询\n",
    "            res_left = self.__query_interval(q_left, q_right, left_index)\n",
    "        if q_right > mid:                           # 在右子树中查询\n",
    "            res_right = self.__query_interval(q_left, q_right, right_index)\n",
    "    \n",
    "        return self.function(res_left, res_right)   # 返回左右子树元素值的聚合计算结果\n",
    "    \n",
    "    # 向上更新实现方法：更新下标为 index 的节点区间值 等于 该节点左右子节点元素值的聚合计算结果\n",
    "    def __pushup(self, index):\n",
    "        left_index = index * 2 + 1                  # 左子节点的存储下标\n",
    "        right_index = index * 2 + 2                 # 右子节点的存储下标\n",
    "        self.tree[index].val = self.function(self.tree[left_index].val, self.tree[right_index].val)\n",
    "        \n",
    "        # 向下更新实现方法：更新下标为 index 的节点所在区间的左右子节点的值和懒惰标记\n",
    "    def __pushdown(self, index):\n",
    "        lazy_tag = self.tree[index].lazy_tag\n",
    "        if lazy_tag is None: \n",
    "            return\n",
    "        \n",
    "        left_index = index * 2 + 1                  # 左子节点的存储下标\n",
    "        right_index = index * 2 + 2                 # 右子节点的存储下标\n",
    "        \n",
    "        if self.tree[left_index].lazy_tag is not None:\n",
    "            self.tree[left_index].lazy_tag += lazy_tag  # 更新左子节点懒惰标记\n",
    "        else:\n",
    "            self.tree[left_index].lazy_tag = lazy_tag\n",
    "        self.tree[left_index].val += lazy_tag\n",
    "        \n",
    "        if self.tree[right_index].lazy_tag is not None:\n",
    "            self.tree[right_index].lazy_tag += lazy_tag # 更新右子节点懒惰标记\n",
    "        else:\n",
    "            self.tree[right_index].lazy_tag = lazy_tag\n",
    "        self.tree[right_index].val += lazy_tag \n",
    "        self.tree[index].lazy_tag = None            # 更新当前节点的懒惰标记\n",
    "        \n",
    "        \n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles) -> bool:\n",
    "        left, right, bottom, top  = math.inf, -math.inf, math.inf, -math.inf\n",
    "        area = 0\n",
    "        x_set, y_set = set(), set()\n",
    "        \n",
    "        for rectangle in rectangles:\n",
    "            x1, y1, x2, y2 = rectangle\n",
    "            left, right = min(left, x1), max(right, x2)\n",
    "            bottom, top  = min(bottom, y1), max(top, y2)\n",
    "            area += (y2 - y1) * (x2 - x1)\n",
    "            x_set.add(x1)\n",
    "            x_set.add(x2)\n",
    "            y_set.add(y1)\n",
    "            y_set.add(y2)\n",
    "            \n",
    "        total_area = (top - bottom) * (right - left)\n",
    "        \n",
    "        if area != total_area:\n",
    "            return False\n",
    "        \n",
    "        x_dict, y_dict = dict(), dict()\n",
    "        \n",
    "        idx = 0\n",
    "        for x in sorted(list(x_set)):\n",
    "            x_dict[x] = idx\n",
    "            idx += 1\n",
    "            \n",
    "        idy = 0\n",
    "        for y in sorted(list(y_set)):\n",
    "            y_dict[y] = idy\n",
    "            idy += 1\n",
    "            \n",
    "            \n",
    "        bottom_dict, top_dict = collections.defaultdict(list), collections.defaultdict(list)\n",
    "        \n",
    "        for i in range(len(rectangles)):\n",
    "            x1, y1, x2, y2 = rectangles[i] \n",
    "            bottom_dict[y_dict[y1]].append(i)\n",
    "            top_dict[y_dict[y2]].append(i)\n",
    "            \n",
    "        self.STree = SegmentTree([0 for _ in range(len(x_set))], lambda x, y: max(x, y))\n",
    "        \n",
    "        for i in range(idy):\n",
    "            for j in top_dict[i]:\n",
    "                start, end = x_dict[rectangles[j][0]], x_dict[rectangles[j][2]]\n",
    "                print('-1', start, end)\n",
    "                self.STree.update_interval(start, end - 1, -1)\n",
    "            for j in bottom_dict[i]:\n",
    "                start, end = x_dict[rectangles[j][0]], x_dict[rectangles[j][2]]\n",
    "                print('+1', start, end)\n",
    "                self.STree.update_interval(start, end - 1, 1)\n",
    "            cnt = self.STree.query_interval(0, len(x_set) - 1)\n",
    "            if cnt  > 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        filters = set()\n",
    "        vet_angs = set()\n",
    "        all_points = set()\n",
    "        for points in rectangles:\n",
    "            i, j, k, l = points\n",
    "            v_a1 = (i, l)\n",
    "            v_a2 = (k, j)\n",
    "            p1 = (i, j)\n",
    "            p2 = (k, l)\n",
    "            vet_angs.add(v_a1)\n",
    "            vet_angs.add(v_a2)\n",
    "            all_points.add(p1)\n",
    "            all_points.add(p2)\n",
    "            fp = (i, j, k)\n",
    "            if fp not in filters:\n",
    "                filters.add(fp)\n",
    "            else:\n",
    "                return False\n",
    "        return len(all_points.difference(vet_angs)) == 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: list[list[int]]) -> bool:\n",
    "        # rectangles=sorted(rectangles,key=lambda x:x[0]+x[1])\n",
    "        tups=tuple([tuple(r) for r in rectangles])\n",
    "        detups=tuple(set(tups))\n",
    "        if len(tups)!=len(detups):\n",
    "            return False\n",
    "        lps=[rect[0:2] for rect in rectangles]\n",
    "        ups=[rect[2:] for rect in rectangles]\n",
    "        minpt=min(lps,key=lambda x:x[0]+x[1])\n",
    "        maxpt=max(ups,key=lambda x:x[0]+x[1])\n",
    "        totalrect=minpt+maxpt\n",
    "        totalarea=area(totalrect)\n",
    "        areas=[area(rect) for rect in rectangles]\n",
    "        if sum(areas)!=totalarea:\n",
    "            return False\n",
    "        ptdic={}\n",
    "        # ptdic_conn={}\n",
    "        for rect in rectangles:\n",
    "            pt=pts(rect)\n",
    "            for k in pt.keys():\n",
    "                lis0=ptdic.get(k)\n",
    "                if lis0 is None:\n",
    "                    ptdic[k]=pt[k]\n",
    "                else:\n",
    "                    ptdic[k]=mergept(lis0,pt[k])\n",
    "        # ptdic_conn={k:sum(v) for k,v in ptdic.items()}\n",
    "        ptlist=[sum(v) for k,v in ptdic.items()]\n",
    "        cnt=Counter(ptlist)\n",
    "        if cnt[2]!=4:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "def mergept(lis0,lis):\n",
    "    return [max([lis0[i],lis[i]]) for i in range(len(lis))]\n",
    "\n",
    "def pts(rect):\n",
    "    r=rect\n",
    "    # direc=['u','d','l','r']\n",
    "    pt= {(r[0],r[1]):[1,0,0,1],\n",
    "         (r[0],r[3]):[0,1,0,1],\n",
    "         (r[2],r[1]):[1,0,1,0],\n",
    "         (r[2],r[3]):[0,1,1,0]}\n",
    "    return pt\n",
    "\n",
    "def area(rect):\n",
    "    return (rect[2]-rect[0])*(rect[3]-rect[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:\n",
    "        x, y, a, b = rectangles[0]\n",
    "        top_left, top_right, down_left, down_right = (x, b), (a, b), (x, y), (a, y)\n",
    "        points = {}\n",
    "        total_area = 0\n",
    "        for rectangle in rectangles:\n",
    "            x, y, a, b = rectangle\n",
    "            total_area += (a - x) * (b - y)\n",
    "            temp_top_left, temp_top_right, temp_down_left, temp_down_right = (x, b), (a, b), (x, y), (a, y)\n",
    "            \n",
    "            if temp_top_left[0] <= top_left[0] and temp_top_left[1] >= top_left[1]:\n",
    "                top_left = temp_top_left\n",
    "            if temp_top_right[0] >= top_right[0] and temp_top_right[1] >= top_right[1]:\n",
    "                top_right = temp_top_right\n",
    "            if temp_down_left[0] <= down_left[0] and temp_down_left[1] <= down_left[1]:\n",
    "                down_left = temp_down_left\n",
    "            if temp_down_right[0] >= down_right[0] and temp_down_right[1] <= down_right[1]:\n",
    "                down_right = temp_down_right\n",
    "\n",
    "            point = points.get(temp_top_left, [[0, 0, 0, 0], 0])\n",
    "            if point[0][0] == 1:\n",
    "                return False\n",
    "            point[0][0] = 1\n",
    "            point[1] += 1\n",
    "            points[temp_top_left] = point\n",
    "\n",
    "            point = points.get(temp_top_right, [[0, 0, 0, 0], 0])\n",
    "            if point[0][1] == 1:\n",
    "                return False\n",
    "            point[0][1] = 1\n",
    "            point[1] += 1\n",
    "            points[temp_top_right] = point\n",
    "\n",
    "            point = points.get(temp_down_left, [[0, 0, 0, 0], 0])\n",
    "            if point[0][2] == 1:\n",
    "                return False\n",
    "            point[0][2] = 1\n",
    "            point[1] += 1\n",
    "            points[temp_down_left] = point\n",
    "\n",
    "            point = points.get(temp_down_right, [[0, 0, 0, 0], 0])\n",
    "            if point[0][3] == 1:\n",
    "                return False\n",
    "            point[0][3] = 1\n",
    "            point[1] += 1\n",
    "            points[temp_down_right] = point\n",
    "\n",
    "        if total_area != (top_right[1] - down_left[1]) * (top_right[0] - down_left[0]):\n",
    "            return False \n",
    "\n",
    "        for pos, point in points.items():\n",
    "            if point[1] == 3:\n",
    "                return False\n",
    "            elif point[1] == 1:\n",
    "                if pos not in [top_left, top_right, down_left, down_right]:\n",
    "                    return False\n",
    "\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\tdef isRectangleCover(self, rectangles: List[List[int]]) -> bool:\r\n",
    "\t\t'''Return bool can it be a rectangle or not'''\r\n",
    "\t\tcoors_all = [(coor[0], coor[1]) for coor in rectangles] + \\\r\n",
    "\t\t\t\t\t[(coor[0], coor[3]) for coor in rectangles] + \\\r\n",
    "\t\t\t\t\t[(coor[2], coor[1]) for coor in rectangles] + \\\r\n",
    "\t\t\t\t\t[(coor[2], coor[3]) for coor in rectangles]\r\n",
    "\t\tcoors_all_counter = Counter(coors_all) # a dict\r\n",
    "\t\tcoor_set = set(coors_all)\r\n",
    "\t\tdel coors_all\r\n",
    "\r\n",
    "\t\tsum_square = sum([(co[2] - co[0]) * (co[3] - co[1]) for co in rectangles])\r\n",
    "\r\n",
    "\t\txs = sorted([coor[0] for coor in rectangles] + [coor[2] for coor in rectangles])\r\n",
    "\t\tys = sorted([coor[1] for coor in rectangles] + [coor[3] for coor in rectangles])\r\n",
    "\t\tleft_down = xs[0], ys[0]\r\n",
    "\t\tleft_up = xs[0], ys[-1]\r\n",
    "\t\tright_down = xs[-1], ys[0]\r\n",
    "\t\tright_up = xs[-1], ys[-1]\r\n",
    "\t\tboarders = {left_down, left_up, right_down, right_up}\r\n",
    "\r\n",
    "\t\ttotal_square = (right_up[0] - left_down[0]) * (right_up[1] - left_down[1])\r\n",
    "\t\t# Compare total_square with sum_square\r\n",
    "\t\tif total_square != sum_square:\r\n",
    "\t\t\treturn False\r\n",
    "\t\t# point doesn't exist\r\n",
    "\t\tif not (left_down in coor_set and \r\n",
    "\t\t\t\tleft_up in coor_set and\r\n",
    "\t\t\t\tright_down in coor_set and\r\n",
    "\t\t\t\tright_up in coor_set\r\n",
    "\t\t\t\t):\r\n",
    "\t\t\treturn False\r\n",
    "\t\tdel coor_set\r\n",
    "\t\t\r\n",
    "\t\tfor coor in coors_all_counter:\r\n",
    "\t\t\t# boarders but not single\r\n",
    "\t\t\tif coor in boarders:\r\n",
    "\t\t\t\tif coors_all_counter[coor] != 1:\r\n",
    "\t\t\t\t\treturn False\r\n",
    "\t\t\t# not boarders but odd\r\n",
    "\t\t\telse:\r\n",
    "\t\t\t\tif coors_all_counter[coor] % 2 != 0:\r\n",
    "\t\t\t\t\treturn False\r\n",
    "\r\n",
    "\t\treturn True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
